Jump to navigation Jump to search
|Problems solvable using sorting|
|This is a stub or unfinished. Contribute by editing me.|
Heap sort is an efficient sorting algorithm implemented with the heap data structure. Time Complexity for all cases is O(n(log n)) and Space Complexity is O(1).
- Build a heap with the sorting array, using recursive insertion.
- Iterate to extract n times the maximum or minimum element in heap and heapify the heap.
- The extracted elements form a sorted subsequence.
Heapsort(A as array) BuildHeap(A) for i = n to 1 swap(A, A[i]) n = n - 1 Heapify(A, 1) BuildHeap(A as array) n = elements_in(A) for i = floor(n/2) to 1 Heapify(A,i,n) Heapify(A as array, i as int, n as int) left = 2i right = 2i+1 if (left <= n) and (A[left] > A[i]) max = left else max = i if (right<=n) and (A[right] > A[max]) max = right if (max != i) swap(A[i], A[max]) Heapify(A, max)
- C in-place non-recursive