VietMX Staff asked 3 years ago
Heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like that algorithm, it divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. The improvement consists of the use of a heap data structure rather than a linear-time search to find the maximum.
A heap is a complete binary tree (every level filled as much as possible beginning at the left side of the tree) that follows this condition: the value of a parent element is always greater than the values of its left and right child elements. So, by taking advantage of this property, we can pop off the max of the heap repeatedly and establish a sorted array.
In an array representation of a heap binary tree, this essentially means that for a parent element with an index of i, its value must be greater than its left child [2i+1] and right child [2i+2] (if it has one).
The HeapSort steps are:
- Create a max heap from the unsorted list
- Swap the max element, located at the root, with the last element
- Re-heapify or rebalance the array again to establish the max heap order. The new root is likely not in its correct place.
- Repeat Steps 2–3 until complete (when the list size is 1)
- Best:
O(n log n) - Average:
O(n log n) - Worst:
O(n log n)
var a = [ 9, 10, 2, 1, 5, 4, 3, 6, 8, 7, 13 ];function swap(a, i, j) { var tmp = a[i]; a[i] = a[j]; a[j] = tmp;}function max_heapify(a, i, length) { while (true) { var left = i*2 + 1; var right = i*2 + 2; var largest = i; if (left < length && a[left] > a[largest]) { largest = left; } if (right < length && a[right] > a[largest]) { largest = right; } if (i == largest) { break; } swap(a, i, largest); i = largest; }}function heapify(a, length) { for (var i = Math.floor(length/2); i >= 0; i--) { max_heapify(a, i, length); }}function heapsort(a) { heapify(a, a.length); for (var i = a.length - 1; i > 0; i--) { swap(a, i, 0); max_heapify(a, 0, i-1); }}heapsort(a);