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
'알고리즘' 카테고리의 다른 글
| 알고리즘_POA (0) | 2021.10.24 |
|---|---|
| 알고리즘_01.기초 (0) | 2021.09.30 |
| 알고리즘_목차 (0) | 2021.09.30 |