Pattern visualizer

Sort Characters By Frequency

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. Animated on: Given a string, sort it in decreasing order based on the frequency of each character. s = "baedcbbbaeeeecc"..

Max-heap of character counts

time O(n + k log k)space O(k)step 1 / 11

d:1

a:2

c:3

b:4

e:5

line 2

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

Where to practice Heap

Practice Heap problems All Heap problems Back to roadmap