DSA Tracker

Visualize

Sort Characters By Frequency

Max-heap of character counts

time O(n + k log k)space O(k)

Count every character, then treat each (character, count) pair as a node in a max-heap ordered by count. Popping the root always gives the most frequent character left, so repeated pops in order build the answer directly.

Details

Animated on: Given a string, sort it in decreasing order based on the frequency of each character. s = "baedcbbbaeeeecc".

Problem:Sort Characters By FrequencyMedium

Max-heap of character counts

step 1 / 11

d:1
a:2
c:3
b:4
e:5

Count every character in "baedcbbbaeeeecc": b:4, a:2, e:5, d:1, c:3. Laid out as a complete binary tree in that order, it is not yet a valid max-heap.

Pseudocode
1FUNCTION sortByFrequency(s):
2  freq <- COUNT each character in s
3  heap <- BUILD max-heap of (char, freq) pairs
4  out <- EMPTY string
5  WHILE heap is not empty:
6    (c, f) <- EXTRACT-MAX(heap)
7    APPEND c REPEATED f TIMES TO out
8  RETURN out
9END FUNCTION

← / → step · space play · Home restart

Every step in words

Show all 11 steps
  1. Count every character in "baedcbbbaeeeecc": b:4, a:2, e:5, d:1, c:3. Laid out as a complete binary tree in that order, it is not yet a valid max-heap.
  2. Heapify index 1: c:3 beats a:2 at index 1, so they swap. c:3 keeps sinking from index 4.
  3. Heapify index 0: e:5 beats b:4 at index 0, so they swap. e:5 keeps sinking from index 2.
  4. Every parent's frequency is now >= both its children's: e:5 >= c:3 >= b:4 >= d:1 >= a:2 down each path. The heap is built in O(n).
  5. b:4 beats a:2 at index 0, so they swap. b:4 keeps sinking from index 2.
  6. Pop the root, e:5 — append 'e' repeated 5 times: out = "eeeee". 4 characters left in the heap.
  7. c:3 beats d:1 at index 0, so they swap. c:3 keeps sinking from index 1.
  8. Pop the root, b:4 — append 'b' repeated 4 times: out = "eeeeebbbb". 3 characters left in the heap.
  9. Pop the root, c:3 — append 'c' repeated 3 times: out = "eeeeebbbbccc". 2 characters left in the heap.
  10. Pop the root, a:2 — append 'a' repeated 2 times: out = "eeeeebbbbcccaa". 1 character left in the heap.
  11. Pop the root, d:1 — append 'd' repeated 1 time: out = "eeeeebbbbcccaad". Heap is empty; done.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Sort Characters By Frequency in the editorAll Heap problemsBack to roadmap