Heap sort algorithm in Data Structures Theory - Full Explanation

Introduction

Sorting a list of items quickly and efficiently is a common problem. Heap sort solves this by using a special tree structure to organize and sort data step-by-step.

Explanation

Heap Structure

A heap is a special kind of binary tree where each parent node is larger (max-heap) or smaller (min-heap) than its children. This property helps quickly find the largest or smallest item. The heap is usually stored as an array for easy access.

A heap organizes data so the largest or smallest item is always easy to find.

Building the Heap

Heap sort starts by turning the unsorted list into a heap. This process arranges the elements so the heap property holds for every parent and child. Building the heap takes time proportional to the number of items.

Building the heap arranges data to prepare for efficient sorting.

Sorting by Extracting

After the heap is built, the largest item (root of max-heap) is swapped with the last item in the list. Then the heap size shrinks by one, and the heap property is restored by moving the new root down. This repeats until all items are sorted.

Sorting happens by repeatedly removing the largest item and fixing the heap.

Time Complexity

Heap sort runs in O(n log n) time for all cases, making it efficient and predictable. It uses no extra space beyond the input list, sorting in place. This makes it useful when memory is limited.

Heap sort is efficient and sorts data in place with consistent speed.

Real World Analogy

Imagine organizing a pile of books so the heaviest book is always on top. You remove the heaviest book one by one, then rearrange the pile so the next heaviest is on top again. This way, you sort the books from heaviest to lightest.

Heap Structure → A pile of books arranged so the heaviest book is always on top

Building the Heap → Stacking the books carefully to make sure the heaviest is on top

Sorting by Extracting → Taking the heaviest book off the pile and restacking the remaining books

Time Complexity → The steady pace of removing and restacking books without extra effort

Diagram

Diagram

       ┌─────────┐
       │   50    │
       ├─────────┤
   ┌───┴───┐ ┌───┴───┐
   │  30   │ │  40   │
 ┌─┴─┐ ┌─┴─┐ ┌─┴─┐ ┌─┴─┐
 │10 │ │20 │ │35 │ │25 │

A max-heap tree showing the largest value at the root and smaller values below, stored as an array. Heap array: [50, 30, 40, 10, 20, 35, 25]

Key Facts

Heap → A binary tree where each parent node is larger (max-heap) or smaller (min-heap) than its children.

Heapify → The process of arranging elements to satisfy the heap property.

In-place Sorting → Sorting the data without needing extra space beyond the original list.

Time Complexity of Heap Sort → Heap sort runs in O(n log n) time for all input cases.

Extract-Max → Removing the largest element from a max-heap and restoring the heap property.

Code Example

Data Structures Theory

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)

    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print(arr)

Common Confusions

Heap sort is the same as quicksort because both are fast.

Heap sort is the same as quicksort because both are fast. Heap sort always runs in O(n log n) time, while quicksort can be slower in worst cases; they use different methods to sort.

A heap is a balanced binary search tree.

A heap is a balanced binary search tree. A heap is a complete binary tree with heap property, but it does not maintain the order of a binary search tree.

Heap sort requires extra memory for the heap.

Heap sort requires extra memory for the heap. Heap sort sorts the array in place and does not need extra memory beyond the input list.

Summary

Heap sort uses a heap data structure to organize and sort data efficiently.

It builds a heap, then repeatedly extracts the largest element to sort the list in place.

Heap sort runs in O(n log n) time and does not require extra memory beyond the input.