# [資演] 12- Binary Heap 與 Heap Sort

###### tags: `資演`

## Binary Heap 簡介
Binary Heap 是在 heap sort 上使用的資料結構。Binary heap 有幾種特性：
* 每個節點最多只能有兩個子節點（所以稱做binary）
* 同一階層要由左到右排列，不能跳過
* 如果是 max-heap 的話，每個節點都要比自己的子節點大（因此根節點最大），如果是 min-heap 則相反

以下是一個max-heap：

因為有了上述的特性，Heap 在實作上就可以用一個 array 來表示，由上到下，由左至右的排列在 array 中：

並且可以直接用index來存取其中的元素，例如，我們現在的節點index為 $i$：
* 左小孩的的 index 就是 $2i + 1$
* 右小孩的 index 就是 $2i + 2$

如果想要得到 parent node 也只要分辨出自己是左小孩還是右小孩，再回推就好了。

## Heap Sort
要怎麼用 Heap 來做排序呢？首先，我們要有一個 min-heap：

然後我們把根節點刪除，放入一個array中，該array代表已經排序好的元素：

現在根節點是空的，我們要把它重新整理成一個合法的 min-heap，稱為 heapify。首先我們把這個heap上的最後一個節點 $7$ 移到根節點的位置：
我們發現這不是一個合法的min-heap，因此需要移動這個 $7$ 到適合的位置。我們的方法是，跟自己的子節點做比較，把3個中最小的跟自己做交換，不斷重複做下去直到變成合法的min-heap：



## Heap 的應用
主要就是用在heap sort上，可以達成 $O(n\log n)$ 的時間複雜度。然而，實務上做排序時還是會以之後會學到的quick sort為主。Heap 另外的重要用途還有作為實現 priority queue 的容器，常與 Dijkstra’s algorithm 一起實作，另外也是解決 k-th largest problem 很實用的資料結構。
## 程式實作
參考[這篇文章](https://favtutor.com/blogs/heap-in-python)。

def max_heapify(A,k):
    l = left(k)
    r = right(k)
    if l < len(A) and A[l] > A[k]:
        largest = l
    else:
        largest = k
    if r < len(A) and A[r] > A[largest]:
        largest = r
    if largest != k:
        A[k], A[largest] = A[largest], A[k]
        max_heapify(A, largest)

def left(k):
    return 2 * k + 1

def right(i):
    return 2 * k + 2

def build_max_heap(A):
    n = int((len(A)//2)-1)
    for k in range(n, -1, -1):
        max_heapify(A,k)

## Python 的 heapq
* `heapq.heappush(heap, item)`
把`item`放進 heap，並保持 heap 性質不變。
* `heapq.heappop(heap)`
從 heap 取出並回傳最小的元素，同時保持 heap 性質不變。。
* `heapq.heapify(x)`
在線性時間內將 list `x` 轉為 heap。

### 使用範例：heapsort

import heapq

def heapsort(x):
    h = []
    for elem in x:
        # 把原list的元素一個一個塞到heap裡
        heapq.heappop(h, elem)    
    return [heapq.heappop(h) for i in range(len(h))]