首页 > 代码库 > 堆排序
堆排序
堆排序（heapsort）是一种原地（in place）排序算法， 它的时间复杂度是O(nlgn). 堆数据结构不只是在堆排序中有用，它还可以构成一个有效的优先队列。
堆数据结构是一种数组对象，它可以被视为一颗完全二叉树。如图：
A
heap-size是放在A中堆的元素个数。根据数组节点的索引，我们可以分别推测节点i的父节点和孩子节点的索引位置
PARENT(i)
return low_round(i/2);
LEFT(i)
return 2i;
RIGHT(i)
return 2i+1;
二叉堆有两种：大根堆和小根堆。大根堆是指除了根以外的每个节点i，有A[PARENT(i)]>=A[i]。也就是说父节点的大小大于其孩子节点的大小。同理可得小根堆：A[PARENT(i)]<=A[i].
对于一种数据结构来说，向其内插入数据或者删除数据都要保持此数据结构的性质。堆数据结构也是这样的，为了保持堆的性质，下面介绍对最大堆进行操作的重要的子程序 MAX-HEAPIFY
一、保持堆的性质
假定以LEFT(i) 和RIGHT(i)为根的两颗二叉树都是大根堆，但这时A[i]可能小于其子女，这样就违反了大根堆的性质。 MAX-HEAPIFY就是让A[i]在大根堆中“下降”，使得以i为根的子树满足大根
堆的性质。
下面贴出伪码：
MAX-HEAPIFY(A, i)
1 l ← LEFT(i)
2 r ← RIGHT(i)
3 if l ≤ heap-size[A] and A[l] > A[i]
4 then largest ← l
5 else largest ← i
6 if r ≤ heap-size[A] and A[r] > A[largest]
7 then largest ← r
8 if largest ≠ i
9 then exchange A[i] <-> A[largest]
10 MAX-HEAPIFY(A, largest)
下图是把4调整到最底层，一趟操作。
由上图，我们很容易看出，初始构造出一最大堆之后，在元素A[i]，即16，大于它的俩个子结点4、10，满足最大堆性质。所以，i下调指向着4,小于,左子14，所以，调用MAX-HEAPIFY，4与其子，14交换位置。但4处在了14原来的位置之后，4小于其右子8，又违反了最大堆的性质，所以再递归调用MAX-HEAPIFY，将4与8，交换位置。于是，满足了最大堆性质，程序结束。
二、建堆
建堆可以使用MAX-HEAPIFY程序自底向上地来将一个数组A[1,...,n]变成一个大根堆。过程BUIDL-MAX-HEAP是对树中的每一个非叶子节点调用一次MAX-HEAPIFY。因为二叉堆是一颗完全二叉树，所以它的叶子节点索引是:A[(round(n/2)+1,... ..., n)]
BUILD-MAX-HEAP(A)
1 heap-size[A] ← length[A]
2 for i ← |_length[A]/2_| downto 1
3 do MAX-HEAPIFY(A, i)
下图是堆的构造过程，首先把数组初始化为一颗完全二叉树，然后调整树的性质。如图：
三、堆排序算法
堆排序算法是利用堆的性质，首先交换根节点和最后一个叶子节点的值，然后减小堆的大小，这样就挑选出来数组中最大的一个元素，然后迭代这个过程。
HEAPSORT(A) ）
1 BUILD-MAX-HEAP(A)
2 for i ← length[A] downto 2
3 do exchange A[1] <-> A[i]
4 heap-size[A] ← heap-size[A] - 1
5 MAX-HEAPIFY(A, 1)
n-1次调用MAX-HEAPIFY，所以，O（n*lgn）
堆排序算法的演示过程（通过，顶端最大的元素与最后一个元素不断的交换，交换后又不断的调用MAX-HEAPIFY以重新维持最大堆的性质，最后，一个一个的，从大到小的，把堆中的所有元素都清理掉，也就形成了一个有序的序列。这就是堆排序的全部过程。）
四、下面列出堆排序的java代码：
package heapSort;import java.util.Arrays;public class HeapSort { public HeapSort(){}; private static int heap_size; public int LEFT(int i){ return 2*i+1; } public int RIGHT(int i){ return 2*i+2; } public int PARENT(int i){ return (i-1)/2; } public void exchange(int[] A, int i, int j){ int temp = A[i]; A[i]=A[j]; A[j]=temp; } public void MAX_HEAPIFY(int[] A, int i){ int l= LEFT(i); int r= RIGHT(i); int largest; 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){ exchange(A, i, largest); MAX_HEAPIFY(A, largest); } } public void BUILD_MAX_HEAP(int[] A){ heap_size=A.length; for(int i = (A.length-1)/2; i>= 0; i--){ MAX_HEAPIFY(A, i); } } public void HEAPSORT(int[] A){ BUILD_MAX_HEAP(A); System.out.println(Arrays.toString(A)); for(int i = A.length-1; i>=0; i--){ exchange(A, 0, i); heap_size= heap_size-1; if(heap_size>1){ MAX_HEAPIFY(A,0); }// System.out.println(i);// System.out.println(Arrays.toString(A)); } System.out.println(Arrays.toString(A)); } public int HEAP_MAXIMUM(int[] A){ return A[0]; } public static void main(String[] args){ int A[]= new int[]{4,1,3,2,16,9,10,14,8,7}; HeapSort arr = new HeapSort(); arr.HEAPSORT(A); }}