學習數據結構與算法的基礎?摘要堆可以分為大頂堆和小頂堆，是根據節點與子節點的比較來界定文章中可以使用數組來存放元素，并處理節點與子節點的比較和交換，就是利用了二叉樹的基礎性質，看完文章相當于再次溫習了二叉樹的基礎性質，今天小編就來說說關于學習數據結構與算法的基礎?下面更多詳細答案一起來看看吧!

學習數據結構與算法的基礎

摘要

堆可以分為大頂堆和小頂堆，是根據節點與子節點的比較來界定。文章中可以使用數組來存放元素，并處理節點與子節點的比較和交換，就是利用了二叉樹的基礎性質，看完文章相當于再次溫習了二叉樹的基礎性質。

堆可以分為大頂堆和小頂堆，大頂堆的定義就是每個節點的值都大于或等于其左右子節點的值。小頂堆和大頂堆相反，即每個節點的值都小于或等于其左右子節點的值。接下來的說明以大頂堆為例。

根據大頂堆的定義可以梳理出這幾點特性：

1. 根節點的值是最大的
2. 節點的左右子節點沒有左子節點值必須小于右子節點值，反之也是沒有限制
3. 節點、它的左子節點、它的右子節點這三個節點中，節點的值是最大的

接下來，咱就用數組來實現大頂堆的數據結構。為什麼要用數組而不是二叉樹來實現？帶着問題，繼續往下看，後面給出答案。

首先創建一個大頂堆的類結構，并定義數組、數量等屬性

public class BinaryHeap<E> { private E[] elements; private int size; }

假設将 elements 數組裡 index 索引中的元素放到合适的位置，這時就要考慮兩點：

1. index 索引位置在葉子節點
2. index 索引位置在非葉子節點

如果是情況1，那就可以不做處理，因為依據特性2來看，子節點之間沒有比較元素的要求，凡是葉子節點，都是子節點，所以葉子節點可以不用處理，等着它的父節點來主動比較。

如果是情況2，那麼就需要和它的左右子節點比較，然後和最大值的節點交換，在編寫邏輯之前，首先要确定以下幾點（假定節點的索引為 index，數組中元素的數量為 size）：

• 非葉子節點的數量 half = size >> 1（half = size / 1）；
• 節點的左子節點索引 leftIndex = (index << 1) 1；
• 節點的右子節點索引 rightIndex = leftIndex 1；

位運算符示例：

x << 1: x *2

x >> 1: x / 2

上面這 3 點都是二叉樹的基本特性，可以看第六期再溫習一下，下面就可以編寫防治 index 索引的節點的代碼：

private void siftDown(int index) { E element = elements[index]; int half = size >> 1; // 取出非葉子節點 // 第一個葉子結點的索引 == 非葉子節點的數量 // 必須保證 index 是非葉子節點 while (index < half) { // index 的節點有2種情況 // 1、隻有左子節點 // 2、同時有左右子節點 // 默認左子節點跟它進行比較 int childIndex = (index << 1) 1; E child = elements[childIndex]; // 右子節點 int rightIndex = childIndex 1; // 保證右子節點存在（rightIndex < size），并比較左右子節點 if (rightIndex < size && compare(elements[rightIndex], child) > 0) { child = elements[ childIndex = rightIndex]; } if (compare(child, element) < 0) break; // 将子節點存放到index位置 elements[index] = child; // 重新設置 index，繼續判斷 index = childIndex; } elements[index] = element; }

看 siftDown 方法的實現邏輯，可以發現是從 index 往下過濾，尋找合适的位置，那麼有沒有從 index 往上過濾呢？上代碼：

private void siftUp(int index) { E e = elements[index]; while (index > 0) { // 得到 index 位置節點的父節點 int pIndex = (index - 1) >> 1; E p = elements[pIndex]; // 節點小于或等于它的父節點時，結束 if (compare(e, p) <= 0) break; // 交換節點元素，父節點設置為 index 節點再進行判斷 elements[index] = p; index = pIndex; } elements[index] = e; }

(index - 1) >> 1 就是獲取父節點索引代碼，也是二叉樹的基本性質。

當解決将 index 索引節點放在合适位置的核心問題之後，就可以處理後面這幾個需求了。

比如，當需要批量添加元素，即直接将一個數組處理成大頂堆時（假設元素已經放入 elements 中 ）：

// 批量建堆 private void heapify() { // 自下而上的下濾，隻需要處理非葉子節點即可 for (int i = (size >> 1) - 1; i >= 0; i--) { siftDown(i); } }

如果使用 siftUp 函數來實現批量建堆，就需要從頭遍曆到最後的位置：

// 批量建堆 private void heapify() { // 自上而下的上濾 for (int i = 0; i < size; i ) { siftUp(i); } }

總結：

• 大頂堆就是每個節點都大于它的左右子節點，小頂堆剛相反；
• 非葉子節點的數量 half = size >> 1（half = size / 1）；
• siftDown 來批量建堆時，可以減少一半的遍曆次數；

,