Algorithm - Heap sort

Heap

heap可看作是幾乎完整的二元樹的陣列。

PARENT(i)
return i/2
LEFT(i)
return 2i
RIGHT(i)
return 2i+1

Max heap與Min heap

Max heap最大的元素在根部
Min heap最小的元素在根部

heapsort用的是Max heap
而priority queue用的則是Min heap，每次取出的會是最小的值。