A Binary Heap is a Complete Binary Tree with following properties :
1.
是一棵Complete Binary Tree.
2.
所有父節點皆≧子節點
(max heap:≧,min heap:≦)
3.
Root具有最大(小)value
(max.heap:大,min.heap:小)Note.
所有Complete Binary Tree 經過 "Heapfy"，就可以成為 Heap
Remark table
Create heap 是使用 bottom up方式，才能達成 O(n)
Applications of Heaps:
1. Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nlogn) time.
2. Priority Queue: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also efficiently.
3. Many problems can be efficiently solved using Heaps. See following for example.
a) K’th Largest Element in an array.
b) Sort an almost sorted array/
c) Merge K Sorted Arrays.
Heap basic Idea
因為Heap為一棵Complete Binary Tree，適合用 1D Array來儲存，可有效降低空間的浪費。
- root 置於 a[1]
- a[i]的parent = a[ i/2 ]
- a[i]的left child = a[2*i]
- a[i]的right child = a[2*i+1]
Heap’s Operation
- Insert(x)… O(logn)
a.將x放在last node 的下一個位置。
b.x往上挑戰父點，直到無父點或是挑戰失敗。
2.ExtraMax…O(logn)
a.將root pop out
b.將last node(x)暫置 root的位置
c.將x往下調整直到符合heap的結構。
There are two ways to build heap which using different methods:
(I.) Top_down Create … O(logn)
依序執行Insert(x)，逐建建立Heap，而在每一過程中皆需要維持Heap的結構
(i.e.每次insert x 都需要檢查是否要調整結構..shift_down())(II.) Bottom_up Create … O(n)
a.將input sequence(data)以Complete B.T 呈現
b.從"the last parent"開始，一路向上往root調整成每個子樹皆為Heap。Heap Sort
Steps
- 先用Bottom-up方式Build Heap …O(N)
- 每回合執行類似Delete_Max的動作 : (每次約O(logN))
a.)SWAP(root,最後一個Node)
b.)Heapfy 成 heap structure3.重複#2. 共(n-1)次 … O(NlogN)
所以，總共時間複雜度為O(N)+O(NlogN)=O(NlogN) [Best/Avg/Worst]
Analysis
- 可被視為使用Heap結構來改善"Selection sort"。
- Unstable Sort
