完全二叉树

如果一颗树是满的，是完全二叉树 完全二叉树只有最后一层可能不是满的 如果一棵树不满，那在不满的一层从左往右也依次是满的，是完全二叉树

从0出发的一段连续的数组，可以被认为是一颗完全二叉树

数组中的i位置： 左孩子位置 = 2 i + 1 右孩子位置 = 2 i + 2 父节点位置 = (i - 1) / 2

大(小)根堆

大根堆：在一棵完全二叉树中，每一棵子树的最大值都是头结点 小根堆：在一棵完全二叉树中，每一棵子树的最小值都是头结点

  1. public static class MyMaxHeap {
  2.     private int[] heap;
  3.     private final int limit;
  4.     private int heapSize;
  6.     public MyMaxHeap(int limit) {
  7.         heap = new int[limit];
  8.         this.limit = limit;
  9.         heapSize = 0;
  10.     }
  12.     public boolean isEmpty() {
  13.         return heapSize == 0;
  14.     }
  16.     public boolean isFull() {
  17.         return heapSize == limit;
  18.     }
  20.     public void push(int value) {
  21.         if (heapSize == limit) {
  22.             throw new RuntimeException("heap is full");
  23.         }
  24.         heap[heapSize] = value;
  25.         // value heapSize
  26.         heapInsert(heap, heapSize++);
  27.     }
  29.     // 用户此时，让你返回最大值，并且在大根堆中，把最大值删掉
  30.     // 剩下的数，依然保持大根堆组织
  31.     public int pop() {
  32.         int ans = heap[0];
  33.         swap(heap, 0, --heapSize);
  34.         heapify(heap, 0, heapSize);
  35.         return ans;
  36.     }
  38.     // 新加进来的数，现在停在了index位置，请依次往上移动，
  39.     // 移动到0位置，或者干不掉自己的父亲了，停！
  40.     private void heapInsert(int[] arr, int index) {
  41.         // [index] [index-1]/2
  42.         // index == 0
  43.         while (arr[index] > arr[(index - 1) / 2]) {
  44.             swap(arr, index, (index - 1) / 2);
  45.             index = (index - 1) / 2;
  46.         }
  47.     }
  49.     // 从index位置，往下看，不断的下沉
  50.     // 停：较大的孩子都不再比index位置的数大；已经没孩子了
  51.     private void heapify(int[] arr, int index, int heapSize) {
  52.         int left = index * 2 + 1;
  53.         while (left < heapSize) { // 如果有左孩子，有没有右孩子，可能有可能没有！
  54.             // 把较大孩子的下标，给largest
  55.             int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
  56.             largest = arr[largest] > arr[index] ? largest : index;
  57.             if (largest == index) {
  58.                 break;
  59.             }
  60.             // index和较大孩子，要互换
  61.             swap(arr, largest, index);
  62.             index = largest;
  63.             left = index * 2 + 1;
  64.         }
  65.     }
  67.     private void swap(int[] arr, int i, int j) {
  68.         int tmp = arr[i];
  69.         arr[i] = arr[j];
  70.         arr[j] = tmp;
  71.     }
  73. }

加强堆

加强内容：

  1. 可以返回是否包含某个元素
  2. 堆中元素值发生变化之后调整堆
  1. /*
  2.  * T一定要是非基础类型，有基础类型需求包一层
  3.  */
  4. public class HeapGreater<T> {
  6.     private ArrayList<T> heap;
  7.     private HashMap<T, Integer> indexMap;
  8.     private int heapSize;
  9.     private Comparator<? super T> comp;
  11.     public HeapGreater(Comparator<? super T> c) {
  12.         heap = new ArrayList<>();
  13.         indexMap = new HashMap<>();
  14.         heapSize = 0;
  15.         comp = c;
  16.     }
  18.     public boolean isEmpty() {
  19.         return heapSize == 0;
  20.     }
  22.     public int size() {
  23.         return heapSize;
  24.     }
  26.     public boolean contains(T obj) {
  27.         return indexMap.containsKey(obj);
  28.     }
  30.     public T peek() {
  31.         return heap.get(0);
  32.     }
  34.     public void push(T obj) {
  35.         heap.add(obj);
  36.         indexMap.put(obj, heapSize);
  37.         heapInsert(heapSize++);
  38.     }
  40.     public T pop() {
  41.         T ans = heap.get(0);
  42.         swap(0, heapSize - 1);
  43.         indexMap.remove(ans);
  44.         heap.remove(--heapSize);
  45.         heapify(0);
  46.         return ans;
  47.     }
  49.     public void remove(T obj) {
  50.         T replace = heap.get(heapSize - 1);
  51.         int index = indexMap.get(obj);
  52.         indexMap.remove(obj);
  53.         heap.remove(--heapSize);
  54.         if (obj != replace) {
  55.             heap.set(index, replace);
  56.             indexMap.put(replace, index);
  57.             resign(replace);
  58.         }
  59.     }
  61.     public void resign(T obj) {
  62.         heapInsert(indexMap.get(obj));
  63.         heapify(indexMap.get(obj));
  64.     }
  66.     // 请返回堆上的所有元素
  67.     public List<T> getAllElements() {
  68.         List<T> ans = new ArrayList<>();
  69.         for (T c : heap) {
  70.             ans.add(c);
  71.         }
  72.         return ans;
  73.     }
  75.     private void heapInsert(int index) {
  76.         while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
  77.             swap(index, (index - 1) / 2);
  78.             index = (index - 1) / 2;
  79.         }
  80.     }
  82.     private void heapify(int index) {
  83.         int left = index * 2 + 1;
  84.         while (left < heapSize) {
  85.             int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
  86.             best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
  87.             if (best == index) {
  88.                 break;
  89.             }
  90.             swap(best, index);
  91.             index = best;
  92.             left = index * 2 + 1;
  93.         }
  94.     }
  96.     private void swap(int i, int j) {
  97.         T o1 = heap.get(i);
  98.         T o2 = heap.get(j);
  99.         heap.set(i, o2);
  100.         heap.set(j, o1);
  101.         indexMap.put(o2, i);
  102.         indexMap.put(o1, j);
  103.     }
  105. }