Heap sort

From Algorithmist
Jump to: navigation, search
Sorting
Algorithms
Bubble sort
Insertion sort
Selection sort
Quicksort
Merge sort
Heap sort
Introsort
Counting sort
Problems
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).

Algorithm[edit]

  1. Build a heap with the sorting array, using recursive insertion.
  2. Iterate to extract n times the maximum or minimum element in heap and heapify the heap.
  3. The extracted elements form a sorted subsequence.

Pseudocode[edit]

Heapsort(A as array)
    BuildHeap(A)
    for i = n to 1
        swap(A[1], 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)

Implementations[edit]

  • C in-place non-recursive