堆排序

堆排序

堆排序算法的演示。首先，将元素进行重排，以符合堆的条件。图中排序过程之前简单的绘出了堆树的结构。
分類	排序算法
數據結構	數組
最差時間復雜度	$O(nlogn)$
最優時間復雜度	$O(nlogn)$
平均時間復雜度	$\Theta(nlog n)$
最差空間復雜度	$O(n)$ total, $O(1)$ auxiliary
最佳算法	不是

堆排序（Heapsort）是指利用堆這種資料結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，並同時滿足堆積的性質：即子結點的键值或索引總是小於（或者大於）它的父節點。

堆節點的訪問

通常堆是通過一維数组來實現的。在起始陣列為 0 的情形中：

• 父節點i的左子節點在位置 (2*i+1);
• 父節點i的右子節點在位置 (2*i+2);
• 子節點i的父節點在位置 floor((i-1)/2);

堆的操作

在堆的資料結構中，堆中的最大值總是位於根節點。堆中定義以下幾種操作：

• 最大堆調整（Max_Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點
• 建立最大堆（Build_Max_Heap）：將堆所有數據重新排序
• 堆排序（HeapSort）：移除位在第一個數據的根節點，並做最大堆調整的遞迴運算

陣列堆積排序

#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
const int HEAP_SIZE = 13; //堆積樹大小
 
int parent(int);
int left(int);
int right(int);
void Max_Heapify(int [], int, int);
void Build_Max_Heap(int []);
void print(int []);
void HeapSort(int [], int);
 
/*父結點*/
int parent(int i)
{
    return (int)floor((i - 1) / 2);
}
 
/*左子結點*/
int left(int i)
{
    return (2 * i + 1);
}
 
/*右子結點*/
int right(int i)
{
    return (2 * i + 2);
}
 
/*單一子結點最大堆積樹調整*/
void Max_Heapify(int A[], int i, int heap_size)
{
    int l = left(i);
    int r = right(i);
    int largest;
    int temp;
    if(l < heap_size && A[l] > A[i])
    {
        largest = l;
    }
    else
    {
        largest = i;
    }
    if(r < heap_size && A[r] > A[largest])
    {
        largest = r;
    }
    if(largest != i)
    {
        temp = A[i];
        A[i] = A[largest];
        A[largest] = temp;
        Max_Heapify(A, largest, heap_size);
    }
}
 
/*建立最大堆積樹*/
void Build_Max_Heap(int A[])
{
    for(int i = (HEAP_SIZE-2)/2; i >= 0; i--)
    {
        Max_Heapify(A, i, HEAP_SIZE);
    }
}
 
/*印出樹狀結構*/
void print(int A[])
{
    for(int i = 0; i < HEAP_SIZE;i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
}
 
/*堆積排序程序碼*/
void HeapSort(int A[], int heap_size)
{
    Build_Max_Heap(A);
    int temp;
    for(int i = heap_size - 1; i >= 0; i--)
    {
        temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        Max_Heapify(A, 0, i);
    }
    print(A);
}
 
/*輸入資料並做堆積排序*/
int main(int argc, char* argv[])
{
    int A[HEAP_SIZE] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
    HeapSort(A, HEAP_SIZE);
    system("pause");
    return 0;
}

其他程序碼

C语言

堆的结构采用陣列实现，起始索引为0。

 #define MAX_HEAP_LEN 100
 static int heap[MAX_HEAP_LEN];
 static int heap_size = 0;              // the number of elements in heaps
 
 static void swap(int* a, int* b)
 {
        int temp = 0;
        temp = *b;
        *b = *a;
        *a = temp;
 }
 
 static void shift_up(int i)
 {
        int done = 0;           
        if( i == 0) return;            //node is the root already
        while((i!=0)&&(!done)) 
        {
                if(heap[i] > heap[(i-1)/2])             
                {//if the current is larger than the parent, then swap
                        swap(&heap[i],&heap[(i-1)/2]);
                }
                else
                {// the job is already done.
                        done =1;
                }
                i = (i-1)/2;
        }
 }
 
 static void shift_down(int i)
 {
        int done = 0;   
        if (2*i + 1> heap_size) return;         // node i is a leaf
 
        while((2*i+1 < heap_size)&&(!done))
        {
                i =2*i+1;                       // jump to left child
                if ((i+1< heap_size) && (heap[i+1] > heap[i]))
                {// find the bigger one of the two children     
                        i++;
                }
                if (heap[(i-1)/2] < heap[i])
                {
                        swap(&heap[(i-1)/2], &heap[i]);
                }
                else
                {
                        done  = 1;
                }
        }
 }                      
 
 static void delete(int i)
 {
        int last = heap[heap_size - 1];     // get the last one;
        heap_size--;                        // shrink the heap
        if (i == heap_size) return;
        heap[i] = last;                     // use the last item to overwrite the current
        shift_down(i);
 }
 
 int delete_max()
 {
        int ret = heap[0];
        delete(0);      
        return ret;  
 }
 
 void insert(int new_data)
 {
        if(heap_size >= MAX_HEAP_LEN) return;  
        heap_size++;
        heap[heap_size - 1] = new_data; 
        shift_up(heap_size - 1); 
 }

C++语言

#include <iostream>
using namespace std;
/*
        #堆排序#%
          #数组实现#%
*/
//#筛选算法#%
void sift(int d[], int ind, int len)
{
        //#置i为要筛选的节点#%
        int i = ind;
 
        //#c中保存i节点的左孩子#%
        int c = i * 2 + 1; //#+1的目的就是为了解决节点从0开始而他的左孩子一直为0的问题#%
 
        while(c < len)//#未筛选到叶子节点#%
        {
                //#如果要筛选的节点既有左孩子又有右孩子并且左孩子值小于右孩子#%
                //#从二者中选出较大的并记录#%
                if(c + 1 < len && d[c] < d[c + 1])
                        c++;
                //#如果要筛选的节点中的值大于左右孩子的较大者则退出#%
                if(d[i] > d[c]) break;
                else
                {
                        //#交换#%
                        int t = d[c];
                        d[c] = d[i];
                        d[i] = t;
                        //
                        //#重置要筛选的节点和要筛选的左孩子#%
                        i = c;
                        c = 2 * i + 1;
                }
        }
 
        return;
}
 
void heap_sort(int d[], int n)
{
        //#初始化建堆, i从最后一个非叶子节点开始#%
        for(int i = (n - 2) / 2; i >= 0; i--)
                sift(d, i, n);
 
        for(int j = 0; j < n; j++)
        {
                //#交换#%
                int t = d[0];
                d[0] = d[n - j - 1];
                d[n - j - 1] = t;
 
                //#筛选编号为0 #%
                sift(d, 0, n - j - 1);
 
        }
}
 
int main()
{
        int a[] = {3, 5, 3, 6, 4, 7, 5, 7, 4}; //#QQ#%
 
        heap_sort(a, sizeof(a) / sizeof(*a));
 
        for(int i = 0; i < sizeof(a) / sizeof(*a); i++)
        {
                cout << a[i] << ' ';
        }
        cout << endl;
    return 0;
}

java语言

public class HeapSort {
        private static int[] sort = new int[]{1,0,10,20,3,5,6,4,9,8,12,17,34,11};
        public static void main(String[] args) {
                buildMaxHeapify(sort);
                heapSort(sort);
                print(sort);
        }
 
        private static void buildMaxHeapify(int[] data){
                //没有子节点的才需要创建最大堆，从最后一个的父节点开始
                int startIndex = getParentIndex(data.length - 1);
                //从尾端开始创建最大堆，每次都是正确的堆
                for (int i = startIndex; i >= 0; i--) {
                        maxHeapify(data, data.length, i);
                }
        }
 
        /**
         * 创建最大堆
         * @param data
         * @param heapSize 需要创建最大堆的大小，一般在sort的时候用到，因为最多值放在末尾，末尾就不再归入最大堆了
         * @param index 当前需要创建最大堆的位置
         */
        private static void maxHeapify(int[] data, int heapSize, int index){
                // 当前点与左右子节点比较
                int left = getChildLeftIndex(index);
                int right = getChildRightIndex(index);
 
                int largest = index;
                if (left < heapSize && data[index] < data[left]) {
                        largest = left;
                }
                if (right < heapSize && data[largest] < data[right]) {
                        largest = right;
                }
                //得到最大值后可能需要交换，如果交换了，其子节点可能就不是最大堆了，需要重新调整
                if (largest != index) {
                        int temp = data[index];
                        data[index] = data[largest];
                        data[largest] = temp;
                        maxHeapify(data, heapSize, largest);
                }
        }
 
        /**
         * 排序，最大值放在末尾，data虽然是最大堆，在排序后就成了递增的
         * @param data
         */
        private static void heapSort(int[] data){
                //末尾与头交换，交换后调整最大堆
                for (int i = data.length - 1; i > 0; i--) {
                        int temp = data[0];
                        data[0] = data[i];
                        data[i] = temp;
                        maxHeapify(data, i, 0);
                }
        }
 
        /**
         * 父节点位置
         * @param current
         * @return
         */
        private static int getParentIndex(int current){
                return (current - 1) >> 1;
        }
 
        /**
         * 左子节点position 注意括号，加法优先级更高
         * @param current
         * @return
         */
        private static int getChildLeftIndex(int current){
                return (current << 1) + 1;
        }
 
        /**
         * 右子节点position
         * @param current
         * @return
         */
        private static int getChildRightIndex(int current){
                return (current << 1) + 2;
        }
 
        private static void print(int[] data){
                int pre = -2;
                for (int i = 0; i < data.length; i++) {
                        if (pre < (int)getLog(i+1)) {
                                pre = (int)getLog(i+1);
                                System.out.println();
                        } 
                        System.out.print(data[i] + " |");
                }
        }
 
        /**
         * 以2为底的对数
         * @param param
         * @return
         */
        private static double getLog(double param){
                return Math.log(param)/Math.log(2);
        }
}

python语言

#!/usr/bin/env python
#-*-coding:utf-8-*-
 
def heap_sort(lst):
    for start in range((len(lst)-2)/2,-1,-1):
        sift_down(lst,start,len(lst)-1)
 
    for end in range(len(lst)-1,0,-1):
        lst[0],lst[end] = lst[end],lst[0]
        sift_down(lst,0,end-1)
    return lst
 
def sift_down(lst,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
 
def main():
    l = [9,2,1,7,6,8,5,3,4]
    heap_sort(l)
 
if __name__ == "__main__":
    main()

in-place堆排序

基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的in-place的堆排序使用了另外一个小技巧。堆排序的过程是：

1. 建立一个堆H[0..n-1]
2. 把堆首（最大值）和堆尾互换
3. 把堆的尺寸缩小1，并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置
4. 重复步骤2，直到堆的尺寸为1

平均复杂度

堆排序的平均时间复杂度为$O(n\mathrm{lg}n)$，空间复杂度为$\Theta(1)$。