Skip to main content
Code ScholarsCodeScholars

Hash Tables, Heaps, and Priority Structures · Sorting

Heap Sort

Heap sort uses heap structure to repeatedly select the next largest or smallest item with predictable O(n log n) behavior.

Enroll NowText UsContact Code ScholarsFull DSA Course

Student Focus

We use heap sort to reinforce why data structure invariants can drive algorithm design.

Guided Lesson Notes

Understanding Heap Sort

Heap Sort focuses on fast lookup, priority selection, and the difference between average-case access and ordered removal. Heap sort uses heap structure to repeatedly select the next largest or smallest item with predictable O(n log n) behavior.

Model: separate the key or priority from the stored value; the structure exists to answer one operation very quickly.

Invariant: a hash table must send equal keys to the same place, while a heap must keep every parent no worse than its children.

Implementation: maps, sets, counters, priority queues, comparators, heapify steps, and careful handling of collisions or ties.

Use Heap Sort when the problem asks for frequencies, duplicates, top-k values, smallest available item, repeated minimum merge, or dynamic priorities.

Visual Model

A small picture for Heap Sort

Hash Table View

0: lime
1: empty
2: pear -> plum
3: apple

Heap View

2479121520

Key Ideas

  • Heapify
  • Repeated removal
  • In-place sorting tradeoffs

Practice Prompts

  • Trace heap sort on a six-element array.
  • Compare heap sort with merge sort and quicksort.

Vocabulary

Terms students should be able to say clearly

Key

The value used to find or group data in a hash table.

Collision

Two keys landing in the same hash-table location.

Load factor

How full a hash table is relative to its capacity.

Priority

The ordering rule used by a priority queue or heap.

Heap property

The parent-child ordering rule maintained by a heap.

Amortized cost

Average cost over many operations, including occasional expensive cleanup.

Worked Example

Worked example: tracing Heap Sort

Trace a small input, focusing on heapify.

  1. 1Write a small input where Heap Sort is clearly useful.
  2. 2Label the part of the input related to Heapify.
  3. 3Perform one operation and explain which invariant is still true afterward.
  4. 4Run a second operation that touches an edge case, such as an empty side, duplicate value, boundary index, disconnected vertex, or tie.
  5. 5Finish by saying which operation dominates the runtime and why.

Complexity Check

Costs students should be able to explain

OperationTypical CostReason
Hash lookupAverage O(1)Good hashing makes key lookup nearly constant on typical inputs.
Heap insert/removeO(log n)A heap restores its invariant along one root-to-leaf path.
Build from all valuesO(n) to O(n log n)The cost depends on whether heapify or repeated insertion is used.

Common Mistakes

What to watch while practicing

  • Coding before drawing the structure or state changes.
  • Forgetting the invariant that makes the algorithm correct.
  • Testing only the sample input and skipping boundary cases.
  • Giving Big-O without explaining which operation dominates the work.

Interview-Style Coding Problem

Heap Sort interview problem: Top K Frequent Values

Interview medium

Problem

Given n integers, print the k values with the highest frequencies. If frequencies tie, the smaller value comes first.

Input

The first line contains n and k. The second line contains n integers.

Output

Print the selected values ordered by descending frequency and ascending value for ties.

Sample Input

8 2
1 1 1 2 2 3 3 4

Sample Output

1 2

Why the sample works

Value 1 appears three times. Values 2 and 3 appear twice, so 2 wins the tie.

Approach

  1. 1Count frequencies with a hash map.
  2. 2Push each value into a priority queue ordered by higher frequency first.
  3. 3Use the value itself as the tie-breaker.
  4. 4Pop k entries to form the answer.

O(n + u log u) time and O(u) extra space, where u is the number of unique values.

Java Solution

import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int k = sc.nextInt();

    Map<Integer, Integer> freq = new HashMap<>();
    for (int i = 0; i < n; i++) {
      int x = sc.nextInt();
      freq.put(x, freq.getOrDefault(x, 0) + 1);
    }

    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
      if (a[1] != b[1]) return b[1] - a[1];
      return a[0] - b[0];
    });

    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
      pq.add(new int[] {entry.getKey(), entry.getValue()});
    }

    for (int i = 0; i < k && !pq.isEmpty(); i++) {
      if (i > 0) System.out.print(" ");
      System.out.print(pq.remove()[0]);
    }
    System.out.println();
  }
}

Python Solution

from collections import Counter
import heapq

n, k = map(int, input().split())
a = list(map(int, input().split()))

freq = Counter(a)
heap = [(-count, value) for value, count in freq.items()]
heapq.heapify(heap)

answer = []
for _ in range(min(k, len(heap))):
    answer.append(heapq.heappop(heap)[1])

print(*answer)

Practice Challenge

Make the idea your own

Create a two-minute explanation of Heap Sort: define it, trace one example, name one edge case, and give the runtime of the main operation.

Tutoring Connection

Need help with this topic?

Bring a question or code attempt to a tutoring session.

Reserve a Free SessionText UsOpen Online Compiler