# Heap sort

Jump to navigation
Jump to 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]

- 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.

## 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