堆

什么是堆？

堆 是一棵 完全二叉樹：即使它不是滿二叉樹，也是正在從左往右變滿的過程中。

1）堆結構就是用數組實現的完全二叉樹結構

2）完全二叉樹中，如果每棵子樹的 最大值都在頂部，是 大根堆

3）完全二叉樹中，如果每棵子樹的 最小值都在頂部，是 小根堆

4）堆結構的 heapInsert 與 heapify 操作

5）堆結構的增大和減少

6）優先級隊列結構，就是堆結構

7）特點：由 N 個數 組成的堆，高度是 log(n)

如何用數組存放堆？

如果從 0 位置開始：

i 層，則

• 左孩子：2 * i + 1
• 右孩子：2 * i + 2
• 父節點：(i - 1) / 2

如果從 1 位置開始：

正是由于可以使用 位運算 來代替 算數運算，效率更高，所以有時候讓下標從 1 開始。

• 左孩子：2 * i （i << 1）
• 右孩子：2 * i + 1 （i << 1 | 1）
• 父節點：i / 2 （i >> 1）

如何將數組轉化成大根堆？—— heapInsert 操作

每在 i 位置加入一個新的節點，都與它的 (i - 1) / 2 位置的父節點比較，如果比父節點大，則交換（并while比較父節點與父父節點）

private void heapInsert(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;} } private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp; }

如何返回并刪除大根堆的最大值，剩余數字依然保持大根堆？—— heapify 操作

將頂部元素取出

將大根堆的最后位置上的元素覆蓋到頂部

while 循環

如果左右孩子中較大的數比當前節點更大，則交換當前節點和較大的孩子節點

如果左孩子下標越界，或左右孩子都不比當前節點大，就停止

// 返回最大值，并在大根堆中把最大值刪掉，剩下的數依然保持大根堆形態 public int pop() {int ans = heap[0];swap(heap, 0, --heapSize);heapify(heap, 0, heapSize);return ans; } // 從index位置開始，不斷的下沉，直到我的孩子都不再比我大，或者我已經沒孩子了，就停止 private void heapify(int[] arr, int index, int heapSize) {int left = index * 2 + 1;while (left < heapSize) {// largest存儲左右孩子 較大者 的下標int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;// largest存儲兩個孩子與父節點 較大者 的下標largest = arr[largest] > arr[index] ? largest : index;if (largest == index) { // 不需要交換的情況break;}swap(arr, largest, index);index = largest;left = index * 2 + 1;} }

堆排序

先讓整個數組都變成大根堆結構，建立堆的過程:

從上到下的方法，時間復雜度為O(N*logN)

從下到上的方法，時間復雜度為O(N)

把堆的最大值和堆末尾的值交換，然后減少堆的大小之后，再去調整堆，一直周而復始，時間復雜度為O(N*logN)

堆的大小減小成0之后，排序完成！

public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) {return;}// 方法1：對數組進行堆排序 O(N*logN)for (int i = 0; i < arr.length; i++) { // O(N)heapInsert(arr, i); // O(logN)}// 方法2：僅將數組轉化成大頂堆 O(n) for (int i = arr.length - 1; i >= 0; i--) {heapify(arr, i, arr.length);} }

語言提供的堆結構 vs 手寫的堆結構，怎么選擇？

取決于你有沒有 動態改信息 的需求！

• 語言提供的堆結構，如果你動態改數據，不保證依然有序

• 手寫堆結構，因為增加了對象的位置表，所以能夠滿足動態改信息的 resign 需求（以后我們的 Dijskra 會用到），而系統自帶的堆結構即使是實現了對數據的修改，時間復雜度也不會好，因為它沒有 hashmap，只能從頂部開始，遍歷每個元素進行 heapify

  public static class MyHeap<T> {private ArrayList<T> heap; // 用動態數組存堆private HashMap<T, Integer> indexMap; // 對象的位置表private int heapSize; // 堆大小private Comparator<? super T> comparator; // 自定義比較器/*...省略push,pop,heapInsert,heapify等...*/public void resign(T value) { // resign操作不需要全量遍歷整個堆int valueIndex = indexMap.get(value);heapInsert(valueIndex); // 這個heapInsert和下面的heapify，只會命中一個，另一個直接返回heapify(valueIndex, heapSize);} } public static void main(String[] args) {myHeap = new MyHeap<>(new StudentComparator());/*...省略s1, s2等new對象過程...*/myHeap.push(s1);myHeap.push(s2);myHeap.push(s3);myHeap.push(s4);myHeap.push(s5);s2.age = 6;myHeap.resign(s2); }

PriorityQueue 底層就是用堆實現的，默認是小根堆

public static void main(String[] args) {// 小根堆PriorityQueue<Integer> heap = new PriorityQueue<>();heap.add(5);heap.add(7);heap.add(3);heap.add(0);heap.add(2);heap.add(5);while (!heap.isEmpty()) { // 排序輸出System.out.println(heap.poll());} }

與堆有關的題目

已知一個幾乎有序的數組。

幾乎有序是指，如果把數組排好順序的話，每個元素移動的距離一定不超過k（假設k=5），并且k相對于數組長度來說是比較小的。

請選擇一個合適的排序策略，對這個數組進行排序。

思路：維護一個大小為 k 的小根堆，每加入一個新數字，先將小根堆的最小值彈出，再把新值放入小根堆中去。

public static void sortedArrDistanceLessK(int[] arr, int k) {if (k == 0) {return;}// 默認小根堆，復雜度：log(k)PriorityQueue<Integer> heap = new PriorityQueue<>();int index = 0;for (; index <= Math.min(arr.length - 1, k - 1); index++) {heap.add(arr[index]);}int i = 0;for (; index < arr.length; i++, index++) {heap.add(arr[index]);arr[i] = heap.poll();}while (!heap.isEmpty()) {arr[i++] = heap.poll();} }

比較器 Comparator

1)比較器的實質就是重載比較運算符

2)比較器可以很好的應用在特殊標準的排序上

3)比較器可以很好的應用在根據特殊標準排序的結構上

4)寫代碼變得異常容易，還用于范型編程

public static class IdAscendingComparator implements Comparator<Student> {// 返回負數，第一個參數排在前面// 返回正數，第二個參數排在前面// 返回0的時候，誰在前面無所謂@Overridepublic int compare(Student o1, Student o2) {return o1.id - o2.id;} } public static void main(String[] args) {Student student1 = new Student("A", 2, 20);Student student2 = new Student("B", 3, 21);Student student3 = new Student("C", 1, 22);Student[] students = new Student[]{student1, student2, student3};Arrays.sort(students, new IdAscendingComparator()); }

用 Comparator 排序：

public static class HeapComp implements Comparator<Integer> {@Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;} } public static void main(String[] args) {Integer[] arr = {5, 4, 3, 2, 7, 9, 1, 0};Arrays.sort(arr, new HeapComp()); } 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的数据结构与算法（二）：堆，大根堆，小根堆，堆排序，比较器详解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。