알고리즘_06.HeapSort

HeapSOrt

O(n lg n) worst case - like merge sort

sorts in place - like insertion sort

combines the best of both algorithms

 

To understand GeapSort, study

Heaps and Heap operations

Priority Queues.

 

Heap A is a nearly complete binary tree.

Height of node = # of edges on a longest simple path from the node down to a leaf.

Height of heap = height of root = 세타(lg n).

 

A heap can be stored as an array A[1..n].

Root of tree is A[1]

Parent of A[i] = A[i/2]

Left child of A[i] = A[2i]

Right child of A[i] = A[2i + 1].

Computing is fast with binary representation implementation.

 

Heap : Property

For max-heaps (largest element at root), max-heap property