Java 堆排序

一、什么是堆

(二叉)堆数据结构式一种数组对象,它可以视为 一颗完全二叉树。树中每个结点与数组中存放该结点值得那个元素对应。树的每一层都是填满的,最后一层除外。
以上图片就是一个堆结构(左侧)与数组(右侧)的对应关系,存储格式依然是数组但是可以把它看成是一个堆结构。需要注意的是图中都是从1开始的,而Java中数组是从0开始的。
任意节点i左右子节点数组索引的计算方法: 左子节点是2i ,右子节点是2i+1。以上图为例如果i=4,左子节点索引值=2*i = 2*4 = 8, 右子节点索引值= 2*i+1 = 2*4+1 = 9。
但是Java中数组是从0开始,所以在Java中i的左右子节点数组索引的计算方法应该是:
左子节点在数组中索引:2i+1
有子节点在数组中索引:2i+2

二、保持堆的性质

二叉堆分两种:最大堆与最小堆。这两种都必须满足堆的特点,而且如果是最大堆必须保证每层中的父节点都必须大于其左右子节点,最小堆规则与其相反。
先来看看如果数组中任意元素进行操作,使其满足最大堆的以上条件。

(1)使数组中任意元素满足最大堆规则的伪码:

[plain]

  1. MAX-HEAPIFY(A, i)  
  2. 1 l ← LEFT(i)  
  3. 2 r ← RIGHT(i)  
  4. 3 if l ≤ heap-size[A] and A[l] > A[i]  
  5. 4    then largest ← l  
  6. 5    else largest ← i  
  7. 6 if r ≤ heap-size[A] and A[r] > A[largest]  
  8. 7    then largest ← r  
  9. 8 if largest ≠ i  
  10. 9    then exchange A[i] <-> A[largest]  
  11. 10         MAX-HEAPIFY(A, largest)   

(2) 以上伪码逐句解释

1. 计算出左子节点索引
2. 计算出右子节点索引
3. 如果左子节点数组索引小于等于数组大小并且左子节点大于父节点
    4. 把左子节点数组索引赋值给largest
    5. 如果不满足3的条件,把当前父节点的数组索引赋值给largest
6. 如果右子节点数组索引小于等与数组大小并且右子节点数组索引大于largest
    7. 如果满足6的条件,右子节点赋值给largest
8. 如果需要交换
      9. 把当前父节点与largest(子节点最大值)进行交换
    10. 把largest节点当做下一次执行的父节点,接着从1开始执行。

(3)伪码的Java代码实现

[java]

  1. private void maxHeapify(int[] a, int i) {  
  2.   
  3.     int largest;  
  4.   
  5.     int leftIndex = 2 * i + 1;  
  6.     int rightIndex = leftIndex + 1;  
  7.   
  8.     if (leftIndex < a.length && a[leftIndex] > a[i]) {  
  9.         largest = leftIndex;  
  10.     } else {  
  11.         largest = i;  
  12.     }  
  13.     if (rightIndex < a.length && a[rightIndex] > a[largest]) {  
  14.         largest = rightIndex;  
  15.     }  
  16.   
  17.     if (largest != i) {  
  18.         swap(a, i, largest);  
  19.         maxHeapify(a, largest);  
  20.     }  
  21. }  
  22.   
  23. public static void main(String[] args) {  
  24.     int[] array = { 1641014793281 };  
  25.   
  26.     HeapSort heapSort = new HeapSort();  
  27.     // Java数组从0开始,第二个元素索引是1  
  28.     heapSort.maxHeapify(array, 1);  
  29.     System.out.println(Arrays.toString(array));  
  30. }  
输入数组:[16, 4, 10, 14, 7, 9, 3, 2, 8, 1]
输出结果:[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

(4)演示i=2时的执行流程

上图是针对堆中i=2父节点进行堆性质的处理,即保证父节点i的左右子节点的值都比其小,以下是图片具体文字描述的步骤:
1. 先看(a)图,当i=2时 array[i] = array[2] = 4
左子节点 array[leftIndex] = array[4] = 14, 判断条件array[leftIndex]  > array[i] = true, 左子节点比父节点值大不满足最大堆的条件。
右子节点array[rightIndex] = array[5] = 7, 判断条件array[rightIndex]  > (父节点与左子节点最大的值,当前是array[leftIndex]) = false, 右子节点比左子节点小,所以左子节点作为父节点满足最大堆的条件。
交换i = 2 与 leftIndex = 4 的值,即上图(b)展示的结果
2. 再看(b)图,由步骤1可以决定i = 2节点已经满足最大堆条件,但是需要再次判断交换后的i=4的值是否满足最大堆条件。
当i=4时 array[i] = array[4] = 4
左子节点 array[leftIndex] = array[8] = 2, 判断条件array[leftIndex]  > array[i] = false, 左子节点满足最大堆的条件。
右子节点array[rightIndex] = array[9] = 8, 判断条件array[rightIndex]  > (父节点与左子节点最大的值,当前是array[i]) = true, 右子节点比父节点值大不满足最大堆的条件。
交换i = 4 与 rightIndex= 9 的值,即上图(c)展示的结果
3. 看(c)图,因为i=9 没有任何左右子节点,所以此次处理结束。

三、创建最大堆

    以上二、保持堆的性质,具体操作目的是保证处理的结点及其所有子节点都满足最大堆的条件,但是每次操作只能保证指定结点满足条件。如果需要完整的最大堆需要对所有结点都进行以上操作,不过为了减少执行次数,堆中最下面一层所有节点需不要进行以上操作,因为最下面一下面一层节点时没有左子节点或者右右子节点的(例如:下图中8,9,10节点),所以length/2-1是按数组先后排序,最后一个父节点的索引(例如:下图中5节点),之后依次递减(例如:下图中5,4,3,2,1)。

(1)创建最大堆伪码

[plain]

  1. BUILD-MAX-HEAP(A)  
  2. 1  heap-size[A] ← length[A]  
  3. 2  for i ← |_length[A]/2_| downto 1  
  4. 3    do MAX-HEAPIFY(A, i)  

(2)创建最大堆Java实现与下图例子处理结果

[java]

  1. public void buildMaxHeap(int[] a, int n) {  
  2.        
  3.       for (int i = n/21 ; i >= 0; i–) {  
  4.            maxHeapify(a, i, n);  
  5.       }  
  6.   
  7.  }  
  8.   
  9.  public static void main(String[] args) {  
  10.       int[] array = {4132169101487};  
  11.       System.out.println( Arrays.toString(array) );  
  12.        
  13.       HeapSort heapSort = new HeapSort();  
  14.       heapSort.buildMaxHeap(array, array.length);  
  15.       System.out.println( Arrays.toString(array) );  
  16.  }  
输入数组:[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
输出结果:[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

3. 最大堆创建过程

以上是一次对i = 5,4,3,2,1节点执行保持最大堆的性质,这里不在一一解释,每个节点保持最大堆可以查看(二、保持最大堆的性质 ->(4)演示i=2时的执行流程)

四、堆排序

    上面已经解释了什么是堆,如果使堆中每个节点波爱吃最大堆的性质,并且也创建了最大堆。以上3个步骤的目的都是为了堆排序准备的,现在有一个疑问最大堆是排序好的数组吗?要想解决这个疑惑可以直接查看三种创建最大的堆的结果,看下其结果([16, 14, 10, 8, 7, 9, 3, 2, 4, 1])是否满足排序要求,猛的一看好像是满足由大到小一次排序,但是其中7与2明显小于右侧的值,所以最大堆并不一定都是排序好的数组。
    最大堆有一个特点,其根节点是堆中最大的,如果能把根节点从堆中移除,再接着把剩余的结点保持最大堆特性,反复移除与保持剩余节点的最大堆操作,因为每次移除的都是剩余节点中值最大的,所以可能创建一个排序好数组。

(1) 堆排序伪码

其中BUILD-MAX-HEAP在(二、保持堆的性质)已经介绍,MAX-HEAPIFY在(三、创建最大堆)已经介绍
[plain]

  1. HEAPSORT(A)  
  2. 1 BUILD-MAX-HEAP(A)  
  3. 2 for i ← length[A] downto 2  
  4. 3    do exchange A[1] <-> A[i]  
  5. 4       heap-size[A] ← heap-size[A] – 1  
  6. 5       MAX-HEAPIFY(A, 1)  

(2)堆排序完整代码

[java] 

  1. public class HeapSort {  
  2.   
  3.      public static void main(String[] args) {  
  4.           int[] array = {4132169101487};  
  5.           System.out.println( Arrays.toString(array) );  
  6.             
  7.           HeapSort heapSort = new HeapSort();  
  8.           heapSort.heapSort(array, array.length);  
  9.           System.out.println( Arrays.toString(array) );  
  10.      }  
  11.        
  12.      public void heapSort(int[] array, int n) {  
  13.           if (array == null) {  
  14.                throw new NullPointerException();  
  15.           }  
  16.           if (n > array.length) {  
  17.                throw new ArrayIndexOutOfBoundsException();  
  18.           }  
  19.             
  20.           buildMaxHeap(array, n);  
  21.             
  22.           for (int i = n-1; i >= 1; i–) {  
  23.                swap(array, 0, i);  
  24.                maxHeapify(array, 0, i);  
  25.           }  
  26.      }  
  27.        
  28.      public void buildMaxHeap(int[] a, int n) {  
  29.             
  30.           for (int i = n/21 ; i >= 0; i–) {  
  31.                maxHeapify(a, i, n);  
  32.           }  
  33.   
  34.      }  
  35.   
  36.      private void maxHeapify(int[] a, int i, int n) {  
  37.             
  38.           int largest;  
  39.             
  40.           int leftIndex = 2 * i + 1;  
  41.           int rightIndex = leftIndex + 1;  
  42.             
  43.           if (leftIndex < n && a[leftIndex] > a[i]) {  
  44.                largest = leftIndex;  
  45.           } else {  
  46.                largest = i;  
  47.           }  
  48.           if (rightIndex < n && a[rightIndex] > a[largest]) {  
  49.                largest = rightIndex;  
  50.           }  
  51.             
  52.           if (largest != i) {  
  53.                swap(a, i, largest);  
  54.                maxHeapify(a, largest, n);  
  55.           }  
  56.      }  
  57.      private void swap(int[] pArray, int pX, int pY) {  
  58.           int temp = pArray[pX];  
  59.           pArray[pX] = pArray[pY];  
  60.           pArray[pY] = temp;  
  61.      }  
  62. }  
注意:maxHeapify方法与上面的不同,增加了参数n堆元素总个数,因为每次移除根后堆的大小都会减去1,所以每次创建最大堆的时候传入堆元素总个数的参数都是移除根后的值。
输入数组:[4, 1, 3, 2, 16, 9, 10, 14, 8, 7]
输出结果:[1, 2, 3, 4, 7, 8, 9, 10, 14, 16]

标签