堆排序

目录导航

堆节点的访问

通常堆是通过一维数组来实现的。在数组起始位置为0的情形中：

父节点i的左子节点在位置;

父节点i的右子节点在位置;

子节点i的父节点在位置;

堆的操作

在堆的数据结构中，堆中的最大值总是位于根节点(在优先队列中使用堆的话堆中的最小值位于根节点)。堆中定义以下几种操作：

最大堆调整（Max_Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点

创建最大堆（Build_Max_Heap）：将堆所有数据重新排序

堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算

实现示例

C语言

#include #include void swap(int* a, int* b) 
{
    int temp = *b; *b = *a; *a = temp;
}
void max_heapify(int arr[], int start, int end) {
    //建立父節點指標和子節點指標 
    int dad = start; 
    int son = dad * 2 + 1; 
    while (son <= end)
    { 
        //若子節點指標在範圍內才做比較 
        if (son + 1 <= end && arr[son] < arr[son + 1])
        //先比較兩個子節點大小，選擇最大的
        son++;  if (arr[dad] > arr[son])
        //如果父節點大於子節點代表調整完畢，直接跳出函數 
        return; 
        else
        { 
            //否則交換父子內容再繼續子節點和孫節點比較  
            swap(&arr;[dad], &arr;[son]); 
            dad = son;
            son = dad * 2 + 1; 
        }
    }
}
void heap_sort(int arr[], int len) {
    int i; 
    //初始化，i從最後一個父節點開始調整 
    for (i = len / 2 - 1; i >= 0; i--) 
    max_heapify(arr, i, len - 1); 
    //先將第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢 
    for (i = len - 1; i > 0; i--)
    {  swap(&arr;[0], &arr;[i]);  
    max_heapify(arr, 0, i - 1); 
    }
}
int main() {
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; 
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len);
    int i; 
    for (i = 0; i < len; i++)  printf("%d ", arr[i]); 
    printf("\n");
    return 0;
}

Cplus

#include
#include using namespace std;
void max_heapify(int arr[], int start, int end)
{ 
    int dad = start; 
    int son = dad * 2 + 1; 
    while (son <= end)
    { 
        if (son + 1 <= end && arr[son] < arr[son + 1])
        son++; 
        if (arr[dad] > arr[son]) 
        return; 
        else
        {
            swap(arr[dad], arr[son]);
            dad = son;   son = dad * 2 + 1;
        }
    }
}
void heap_sort(int arr[], int len) 
{
    for (int i = len / 2 - 1; i >= 0; i--) 
    max_heapify(arr, i, len - 1);
    for (int i = len - 1; i > 0; i--) 
    { 
        swap(arr[0], arr[i]); 
        max_heapify(arr, 0, i - 1); 
    }
}
int main()
{ 
    int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; 
    int len = (int) sizeof(arr) / sizeof(*arr);
    heap_sort(arr, len); 
    for (int i = 0; i < len; i++)  
    cout << arr[i] << '    '
    cout << endl; return 0;
}

Java

import java.util.Arrays;
public class HeapSort {      
    private int[] arr; 
    public HeapSort(int[] arr)    {       
        this.arr = arr;  
    }     
        /**     * 堆排序的主要入口方法，共两步。          */    public void sort(){     
            /*                  *  第一步：将数组堆化                *  beginIndex = 第一个非叶子节点。              *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。              *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。            */     
            int len = arr.length - 1;
            int beginIndex = (len - 1) >> 1;   
            for(int i = beginIndex; i >= 0; i--)
            {        
                maxHeapify(i, len);
            }           
            /*                * 第二步：对堆化数据排序              * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。            * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。              * 直至未排序的堆长度为 0。                  */      
            for(int i = len; i > 0; i--)
            { 
                swap(0, i);  
                maxHeapify(0, i - 1); 
            } 
        }     
        private void swap(int i,int j)        {      
            int temp = arr[i]; 
            arr[i] = arr[j];
            arr[j] = temp;    
        }      
        /**          * 调整索引为 index 处的数据，使其符合堆的特性。          *            * @param index 需要堆化处理的数据的索引          * @param len 未排序的堆（数组）的长度          */   
        private void maxHeapify(int index,int len)        {  
            int li = (index << 1) + 1; 
            // 左子节点索引      
            int ri = li + 1;        
            // 右子节点索引       
            int cMax = li;      
            // 子节点值最大索引，默认左子节点。
            if(li > len) return;     
            // 左子节点索引超出计算范围，直接返回。 
            if(ri <= len && arr[ri] > arr[li]) 
            // 先判断左右子节点，哪个较大。   
            cMax = ri;      
            if(arr[cMax] > arr[index])
            {        
                swap(cMax, index);  
                // 如果父节点被子节点调换，   
                maxHeapify(cMax, len);
                // 则需要继续判断换下后的父节点是否符合堆的特性。 
            }    
        }      
        /**            * 测试用例        *            * 输出：          * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]          */ 
        public static void main(String[] args)        {   
            int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};         
            new HeapSort(arr).sort();    
            System.out.println(Arrays.toString(arr));    
        }    
}

Python

#!/usr/bin/env python#-*-coding:utf-8-*-def heap_sort(lst):
def sift_down(start, end):    
"""最大堆调整"""     
root = start     
while True:        
child = 2 * root + 1   
if child > end:            
break        
if child + 1 <= end and lst[child] < lst[child + 1]:    
child += 1      
if lst[root] < lst[child]:          
lst[root], lst[child] = lst[child], lst[root]           
root = child        
else:         
break 
# 创建最大堆    
for start in xrange((len(lst) - 2) // 2, -1, -1):   
    sift_down(start, len(lst) - 1)  
    # 堆排序    for end in xrange(len(lst) - 1, 0, -1):   
    lst[0], lst[end] = lst[end], lst[0]  
    sift_down(0, end - 1)    return lst      
    def main():  
        l = [9,2,1,7,6,8,5,3,4]   
        heap_sort(l)if __name__ == "__main__":  
            main()

JavaScript

Array.prototype.heap_sort = function() { 
    var arr = this.slice(0); function swap(i, j)    {  
       ar tmp = arr[i];  arr[i] = arr[j];  arr[j] = tmp; 
    }
    function max_heapify(start, end)    {  
        //建立父節點指標和子節點指標 
        var dad = start; 
        var son = dad * 2 + 1; 
        if (son >= end)
        //若子節點指標超過範圍直接跳出函數 
        return; 
        if (son + 1 < end && arr[son] < arr[son + 1])
        //先比較兩個子節點大小，選擇最大的   son++;
        if (arr[dad] <= arr[son])
        {
            //如果父節點小於子節點時，交換父子內容再繼續子節點和孫節點比較   
            swap(dad, son);
            max_heapify(son, end); 
        } 
    } 
    var len = arr.length;
    //初始化，i從最後一個父節點開始調整
    for (var i = Math.floor(len / 2) - 1; i >= 0; i--) 
    max_heapify(i, len); 
    //先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢
    for (var i = len - 1; i > 0; i--) 
    {
        swap(0, i); 
        max_heapify(0, i); 
    }
    return arr;
}
var a = [3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6];
console.log(a.heap_sort());

PHP

= $end)
//若子節點指標超過範圍直接跳出函數 
return;
if ($son + 1 < $end && $arr[$son] < $arr[$son + 1])
//先比較兩個子節點大小，選擇最大的 
$son++; if ($arr[$dad] <= $arr[$son])
{
//如果父節點小於子節點時，交換父子內容再繼續子節點和孫節點比較 
swap($arr[$dad], $arr[$son]);
max_heapify($arr, $son, $end);
}}function heap_sort($arr) {
$len = count($arr);
//初始化，i從最後一個父節點開始調整
for ($i = ceil($len/2) - 1; $i >= 0; $i--)
max_heapify($arr, $i, $len);
//先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢 
for ($i = $len - 1; $i > 0; $i--)
{ 
swap($arr[0], $arr[$i]);  max_heapify($arr, 0, $i); 
} return $arr;
}$arr = array(3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6);
$arr = heap_sort($arr);
for ($i = 0; $i < count($arr);
$i++) echo $arr[$i] .
' ';?>

Go

package mainimport ( "fmt")func HeapSort(array []int) { m := len(array) s := m/2 for i := s; i > -1; i--
{  
    heap(array, i, m-1) 
}
for i := m-1; i > 0; i-- 
{
    array[i], array[0] = array[0], array[i]  heap(array, 0, i-1) 
}
}
func heap(array []int, i, end int)
{
    l := 2*i+1 if l > end 
    {  
        return 
    }
    n := l r := 2*i+2 if r <= end && array[r]>array[l]
    {
        n = r
    } if array[i] > array[n]
    {
        return
    } array[n], array[i] = array[i], array[n] heap(array, n, end)}func main() 
    {
        array := []int{  55, 94,87,1,4,32,11,77,39,42,64,53,70,12,9, } 
        HeapSort(array)
        fmt.Println(array)
    }