大根堆

  1. public class Heap {
  3.     int[] nums = new int[10];
  5.     int heapSize = 0;
  7.     public static void main(String[] args) {
  8.         Heap heap = new Heap();
  9.         heap.add(4);
  10.         heap.add(1);
  11.         heap.add(3);
  12.         heap.add(6);
  13.         heap.add(2);
  14.         heap.add(9);
  15.         heap.add(4);
  16.         // 9
  17.         int remove1 = heap.remove();
  18.         // 6
  19.         int remove2 = heap.remove();
  20.         // 4
  21.         int remove3 = heap.remove();
  22.         // 4
  23.         int remove4 = heap.remove();
  24.         // 3
  25.         int remove5 = heap.remove();
  26.         heap.add(10);
  27.         // 10
  28.         int remove6 = heap.remove();
  29.         System.out.println();
  30.     }
  32.     private void add(int num){
  33.         if (heapSize == nums.length){
  34.             synchronized (nums){
  35.                 int[] numsNew = new int[nums.length + 10];
  36.                 System.arraycopy(nums,0,numsNew,0,nums.length);
  37.                 nums = numsNew;
  38.             }
  39.         }
  40.         nums[heapSize] = num;
  41.         up(heapSize);
  42.         heapSize++;
  43.     }
  45.     private int remove(){
  46.         int num = nums[0];
  47.         nums[0] = nums[--heapSize];
  48.         down(0);
  49.         return num;
  50.     }
  53.     /**
  54.      * index位置和父节点比较，大于父节点就交换
  55.      */
  56.     private void up(int index){
  57.         int parentIndex = (index-1)/2;
  58.         while (nums[index] > nums[parentIndex]){
  59.             swap(nums,index,parentIndex);
  60.             index = parentIndex;
  61.             parentIndex = (index-1)/2;
  62.         }
  63.     }
  65.     /**
  66.      * index和子节点比较，子节点先选出最大的，然后和index比较，index小的话则交换
  67.      */
  68.     private void down(int index){
  69.         int leftChildIndex = 2 * index + 1;
  70.         while (leftChildIndex < heapSize){
  71.             int maxChildIndex= leftChildIndex;
  72.             if (leftChildIndex + 1 < heapSize && nums[leftChildIndex] < nums[leftChildIndex+1]){
  73.                 maxChildIndex++;
  74.             }
  75.             if (nums[index] >= nums[maxChildIndex]){
  76.                 return;
  77.             }
  78.             swap(nums,index,maxChildIndex);
  79.             index = maxChildIndex;
  80.             leftChildIndex = 2 * index + 1;
  81.         }
  82.     }
  84.     private void swap(int[] nums, int i, int j){
  85.         if (i == j) {
  86.             return;
  87.         }
  88.         int temp = nums[i];
  89.         nums[i] = nums[j];
  90.         nums[j] = temp;
  91.     }
  93. }

堆排序

从后往前做下调动作，这样能减少调整次数。调整完后变成一个大根堆
然后堆顶元素和最后元素做交换，堆空间减少1，然后让堆顶元素下沉调整。

  1. private void sort(int[] nums){
  2.         this.nums = nums;
  3.         heapSize = nums.length;
  4.         //构建大根堆
  5.         for (int i = nums.length-1; i >= 0; i--) {
  6.             down(i);
  7.         }
  8.         //堆顶是最大值，直接放在最后，然后减少对size，在新size上对目前堆顶的元素进行调整
  9.         while (heapSize > 0){
  10.             swap(nums,0,--heapSize);
  11.             down(0);
  12.         }
  13. }