堆排序

维基百科,自由的百科全书
跳转至: 导航搜索
堆排序
Sorting heapsort anim.gif
堆排序算法的演示。首先,将元素进行重排,以符合堆的条件。图中排序过程之前简单的绘出了堆树的结构。
分類 排序算法
數據結構 數組
最差時間複雜度 O(nlogn)
最優時間複雜度 O(nlogn)[1]
平均時間複雜度 \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;
 
int parent(int);
int left(int);
int right(int);
void Max_Heapify(int [], int, int);
void Build_Max_Heap(int [], int);
void print(int [], 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[]int heap_size)
{
    for(int i = (heap_size-2)/2; i >= 0; i--)
    {
        Max_Heapify(A, i, heap_size);
    }
}
 
/*印出樹狀結構*/
void print(int A[]int heap_size)
{
    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, heap_size);
    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, heap_size);
}
 
/*輸入資料並做堆積排序*/
int main(int argc, char* argv[])
{
    const int heap_size = 13;
    int A[] = {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 = *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()

JavaScript[编辑]

/**
 * Author Jenas zhang
 */
Array.prototype.buildMaxHeap = function() {
    for (var i = Math.floor(this.length/2) -1; i >= 0; i--) {
        this.heapAdjust(i, this.length);
    }
};
 
Array.prototype.swap = function(i, j) {
    var tmp = this[i];
    this[i] = this[j];
    this[j] = tmp;
};
 
Array.prototype.heapSort = function() {
    this.buildMaxHeap();
    for (var i = this.length -1; i > 0; i--) {
        this.swap(0, i);
        this.heapAdjust(0, i);
    }
 
    return this;
};
 
Array.prototype.heapAdjust = function(i, j) {
    var largest = i;
    var left = 2*i + 1;
    var right = 2*i + 2;
 
    if (left < j && this[largest] < this[left]) {
        largest = left;
    }
 
    if (right < j && this[largest] < this[right]) {
        largest = right;
    }
 
    if (largest != i) {
        this.swap(i, largest);
        this.heapAdjust(largest, j);
    }
};
 
var a = new Array();
[].push.apply(a, [2,3,89,57,23,72,43,105]);
console.log(a.heapSort());

原地堆排序[编辑]

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

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

平均复杂度[编辑]

堆排序的平均时间复杂度O(n\mathrm{log}n)空间复杂度\Theta(1)

參考[编辑]