1.堆

1.堆结构就是用数组实现的完全二叉树结构
2.完全二叉树中如果每颗子树的最大值都在顶部就是大根堆
3.完全二叉树中如果每颗子树的最小值都在顶部就是小根堆
4.堆结构的heapInsert与heapify操作
5.堆结构的增大与减少
6.优先级队列结构，就是堆结构
二叉树：image.png size：7 i位置的左孩子：(i2+1) i位置的右孩子 (i 2 + 2) i的父位置：i-1/2
从0出发 由size说明是连续的几个数，就可以看成是完全二叉树。

堆操作的两个调整：heapInsert、heapify。
heapInsert代码：

  1. public class heapInsert {
  2.     public static void heapInsert(int[] arr, int index) {
  3.         while (arr[index] > arr[(index-1)/2]) {
  4.             sawp(arr, index, (index - 1) / 2);
  5.             index = (index - 1) / 2;
  6.         }
  7.     }
  8. }

heapify代码：

  2. public class heapify {
  3.     public static void heapify(int[] arr, int index, int heapSize){
  4.         int left = index * 2 + 1;  // 左孩子的下标
  5.         while(left < heapSize){ // 下方还有孩子
  6.             // 两个孩子中，谁的值大，把下标给largest
  7.             int largest = left + 1 < heapSize && arr[left + 1] > arr[left] 
  8.                     ? left + 1 : left;
  9.             // 父和孩子之间，谁的值大，把下标给largest
  10.             largest = arr[largest] > arr[index] ? largest : index;
  11.             if(largest == index){
  12.                 break;
  13.             }
  14.             swap(arr, largest, index);
  15.             index = largest;
  16.             left = index * 2 + 1;
  17.         }
  18.     }
  19. }

完全二叉树的高度: logN级别。

2.堆排序

  2. public class heapSort {
  3.     public static void heapSort(int[] arr){
  4.         if(arr == null || arr.length == 2){
  5.             return;
  6.         }
  7. //        for(int i = 0; i < arr.length; i++){
  8. //            heapInsert(arr, i);
  9. //        }
  10. //        如果只是单纯的将一个数组拼成大根堆用下边的算法更好
  11.         for(int i = arr.length -1; i >= 0; i--){
  12.             heapify(arr, i, arr.length);
  13.         }
  14.         int heapSize = arr.length;
  15.         swap(arr, 0, --heapSize);
  16.         while(heapSize > 0){
  17.             heapify(arr, 0, heapSize);
  18.             swap(arr, 0, --heapSize);
  19.         }
  20.     }
  21.     public static void heapInsert(int[] arr, int index) {
  22.         while (arr[index] > arr[(index-1)/2]) {
  23.             swap(arr, index, (index - 1) / 2);
  24.             index = (index - 1) / 2;
  25.         }
  26.     }
  27.     public static void heapify(int[] arr, int index, int heapSize){
  28.         int left = index * 2 + 1;  // 左孩子的下标
  29.         while(left < heapSize){ // 下方还有孩子
  30.             // 两个孩子中，谁的值大，把下标给largest
  31.             int largest = left + 1 < heapSize && arr[left + 1] > arr[left] 
  32.                     ? left + 1 : left;
  33.             // 父和孩子之间，谁的值大，把下标给largest
  34.             largest = arr[largest] > arr[index] ? largest : index;
  35.             if(largest == index){
  36.                 break;
  37.             }
  38.             swap(arr, largest, index);
  39.             index = largest;
  40.             left = index * 2 + 1;
  41.         }
  42.     }
  43.     public static void swap(int[] arr, int x, int y) {
  44.         int temp = arr[x];
  45.         arr[x] = arr[y];
  46.         arr[y] = temp;
  47.     }
  48. }