Heapsort

Heapsort is a comparison-based sorting algorithm that builds a heap, then repeatedly removes its extremal element to produce a sorted sequence. It runs in O(n log n) time and sorts in place.

Binary heap: A complete binary tree whose keys obey a heap-order rule between each parent and its children. Heapsort commonly stores its working heap in an array representing this tree.
Comparison sort: A sorting algorithm whose decisions about element order come from pairwise comparisons. Heapsort belongs to this family, so its worst-case comparison count has a logarithmic lower bound.
Quicksort: A sorting algorithm that partitions elements around pivots and recursively sorts the resulting regions. Quicksort is often faster in practice, but its ordinary form lacks heapsort’s worst-case time guarantee.
Worst-case time complexity: The maximum running time of an algorithm over inputs of a given size. Heapsort’s worst-case running time remains O(n log n), regardless of input order.
Heapify: An operation that rearranges elements so a tree or array satisfies the heap-order property. Heap construction establishes the property heapsort needs before extracting elements.
Complete binary tree: A binary tree in which every level is full except possibly the last, which fills from left to right. This shape keeps a heap compact and its height logarithmic in the number of elements.
Merge sort: A stable sorting algorithm that divides data, sorts the parts, and merges them. Merge sort shares O(n log n) worst-case time but usually requires additional storage.
Space complexity: The amount of memory an algorithm uses as a function of input size. Its in-place implementation uses constant auxiliary space, a practical advantage over merge sort.
Sift-down: A heap operation that moves a node downward until the heap-order property is restored. After each extraction, heapsort uses this repair to restore the reduced heap.
Heap property: The rule that each parent in a heap is ordered relative to its children. The heap property makes the root the largest or smallest element available for extraction.

Linked from 4 pages