Heaps
- A binary heap is a nearly complete binary tree without child-parent pointers, usually stored as an array.
- Each node (array element) contains a value (key) and perhaps data associated with the key.
- The tree is completely filled on all levels except possibly the lowest (bottom) level, which is filled from the left(Array indexes are assigned top to bottom, left to right).
Two types of heaps: the max-heap and the min-heap
For a max-heap: every node other than the root has a key less than or equal to the key in its parent.
For a min-heap: every node other than the root has a key greater than or equal to the key in its parent.
Basic properties of a max-heap:
- The key in the root is the largest key.
- Given any node in a max-heap, the node and all its descendants form a max-heap, (i.e., the subtree rooted at the node is a maximum heap, too).
Heaps operation
我們常用兩個方式來操作：
- Swap up. If a key is greater than the key of its parent, swap them.
- Swap down. If a key is less than the key of one of its two children (or a child), swap the key with the larger key of the two children.
MAX-HEAPIFY operation
Make the subtree rooted at i into a max-heap, assuming that the subtrees rooted at LEFT(i) and RIGHT(i) are max-heaps already.
Method: swap down.
Time required: O(logn).
The height of an element is the distance（logn） to the bottom level.
即 O(height)
BUILD-MAX-HEAP operation
Given an unordered array A, turn it into a max-heap.
The idea: fix one element at a time, working from the leaves up to the root. As each element’s turn comes, its children are already fixed.
時間復雜度為O(n)盏浙。
Heapsort
Method: Turn the array into a max-heap. Then repeatedly remove the maximum element of the heap into the proper place in the array.
Time required: <= O(n) + (n - 1)*O(logn) = O(nlogn)
Priority Queues
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called the key.
A max-priority queue supports the following operations.
INSERT(S, x) inserts the element x into the set S, i.e., S ← S ∪ {x}.
MAXIMUM(S) returns the element of S with the largest key.
EXTRACT-MAX(S) removes and returns the element of S with the largest key.
過程：在寫code時威酒，先將root（a[0]）和lastnode(a[last]) exchange, 輸出最后一個node，然后執(zhí)行 heapsize - 1家夺。最后對新的heap進行排位（比較children天试，取大的值和root替換）。
原因：我們用數(shù)組實現(xiàn)heap。INCREASE-KEY(S,x,k) increases the value of element x’s key to the new value k, which is assumed to be at least as large as x’s current key value.
We can implement the operations of a max-priority queue S, using a max-heap A.
- HEAP-MAXIMUM(A) ---O(1)
- HEAP-EXTRACT-MAX(A) --- O(logn) using MAX-HEAPIFY(A, 1)
- HEAP-INCREASE-KEY(A, i, key) --- O(logn)
- MAX-HEAP-INSERT(A, key) --- O(logn) using HEAP-INCREASE-KEY(A,heap size[A],key)
總結
Heapsort is an in place sorting algorithm that runs in O(nlogn).
- It achieves asymptotically optimal running time
- It only takes a constant amount of space outside the input array
- The heapsort algorithm uses the heap data structure, which can also be used for minimum/maximum priority queues
- It is an optimal sorting algorithm
