二叉堆

習題預習

1. 如何實作一個最小Binary Heap？
2. 在一個Binary Heap中，如何找到某個節點的父節點、左子節點和右子節點？
3. 如何在一個Binary Heap中插入一個新的元素，並保持堆的特性？
4. 如何從一個Binary Heap中刪除最小的元素，並保持堆的特性？
5. 如何使用Binary Heap實作堆排序？

說明知識

Binary Heap是一种特殊的二叉树结构，它满足以下两个条件：

1. 父节点的值总是小于或者大于子节点的值，对于小于子节点的情况我们称之为最小堆，对于大于子节点的情况我们称之为最大堆。

2. 它是一棵完全二叉树，也就是除了最后一层，其他层上的节点都是满的，最后一层上的节点都靠左排列。

Binary Heap是一种非常有用的数据结构，通常被用来实现优先队列等高效的算法。

以下是一个最小堆的例子：

           4
         /   \
        9     7
       / \   / \
     10  15 12  20

在这个二叉树中，根节点的值为4，它小于它的所有子节点的值。此外，这个二叉树也满足完全二叉树的条件，因为除了最后一层，其他层上的节点都是满的，最后一层上的节点也是靠左排列。

当我们把这个二叉树表示成一个数组时，它的结构如下：

index: 0 1 2 3 4 5 6
value: 4 9 7 10 15 12 20

在上述表示中，根据完全二叉树的性质，我们可以用下标来表示一个节点的位置，例如节点4的下标为0，节点9的下标为1，等等。这个数组实际上是一个满足最小堆的性质的数组，我们可以利用这个数组来实现堆排序等高效的算法。

彙總重點

1. Binary Heap是一種樹狀資料結構，其中每個節點有最多兩個子節點，每個子節點都有一個父節點。
2. Binary Heap可以分為最大堆和最小堆兩種形式。
3. 在最大堆中，每個父節點的值都大於等於它的子節點的值，而在最小堆中，每個父節點的值都小於等於它的子節點的值。
4. Binary Heap的插入和刪除操作都需要維護堆的性質，以確保堆的正確性。
5. Binary Heap可以用來實現優先級佇列和堆排序等常見的演算法。
6. 在最大堆中，最小元素總是位於根節點，而在最小堆中，最大元素總是位於根節點。
7. Binary Heap的高度是O(log n)，其中n是堆中元素的數量。
8. 二進位樹的節點的位置與陣列元素的位置有關，可以用陣列來實現堆。在堆中元素存儲在一個數組中，並按照二進制樹的層序存儲。

知識測驗

1. 實現一個二叉堆，支持插入、刪除、查找最大值、查找最小值操作。

答案:

答案會根據編程語言不同而不同，實現方式可以參考Visualgo網站的二叉堆實現代碼

2. 求二叉堆中所有元素的中位數。

答案:

可以用兩個二叉堆，一個大根堆，一個小根堆來實現。大根堆存放前半部分數據，小根堆存放後半部分數據。當數據總數為奇數時，中位數就是大根堆的堆頂；當數據總數為偶數時，中位數就是兩個堆的堆頂的平均值。

3. 實現一個求前K大數的算法，限制內存大小，基於堆實現。

答案:

可以使用小根堆來實現。先把前K個數建成大小為K的小根堆，然後對於剩餘的數，如果比堆頂的數要大，就把堆頂的數刪除，然後把該數插入堆中。最終堆中剩餘的就是前K大的數。

4. 求二叉堆的高度。

答案:

可以使用遞歸的方式實現。若二叉堆為空，返回0；否則返回左子樹和右子樹高度的較大值加1。

5. 實現一個由無序數組構建二叉堆的算法。

答案:

首先將無序數組構建成完全二叉樹，然後從最後一個非葉子節點開始，從右到左，逐個進行下沉操作，將每個節點下沉到合適的位置，直到根節點下沉到滿足堆的性質為止。