Heap Sort Implementations in Python: Examples and Explanations
Heap Sort Implementations in Python
The following code samples demonstrate several heap sort implementations in Python, including min-heap and max-heap variants, along with related problems such as merging heaps, finding the closest pair of values, sorting dates, and sorting students by their weighted grade average.
Custom Alphabet Heap Sort
The first example maps each character to its index in a custom alphabet and sorts the characters using a min-heap.
a = [‘z’, ‘y’, ‘x’, ‘w’, ‘v’, ‘t’, ‘s’, ‘r’, ‘q’, ‘p’, ‘n’, ‘m’, ‘l’, ‘k’, ‘j’, ‘h’, ‘g’, ‘f’, ‘d’, ‘c’, ‘b’, ‘u’, ‘o’, ‘i’, ‘e’, ‘a’]
n = int(input())
h = []
for i in input():
h.append(a.index(i))
def heapify(heap, i, n):
l = 2*i + 1
r = 2*i + 2
minid = i
if l < n and heap[l] < heap[minid]:
minid = l
if r < n and heap[r] < heap[minid]:
minid = r
if minid != i:
heap[i], heap[minid] = heap[minid], heap[i]
heapify(heap, minid, n)
def hs(heap):
n = len(heap)
for i in range(n // 2 – 1, -1, -1):
heapify(heap, i, n)
for i in range(n – 1, 0, -1):
heap[0], heap[i] = heap[i], heap[0]
heapify(heap, 0, i)
hs(h)
print(”.join(a[i] for i in h))
Intersection of Two Sorted Heaps
This version reads two arrays from standard input, sorts each with a max-heap, and outputs their common elements.
import sys
def solve():
data = sys.stdin.read().split()
if not data:
return
n = int(data[0])
m = int(data[1])
h1 = list(map(int, data[2:2+n]))
h2 = list(map(int, data[2+n:2+n+m]))
res = []
def hs(heap):
n = len(heap)
h = heap
for i in range(n // 2 – 1, -1, -1):
temp = h[i]
curr = i
while True:
l = 2 * curr + 1
r = l + 1
if l >= n:
break
if r < n and h[r] > h[l]:
maxid = r
else:
maxid = l
if h[maxid] > temp:
h[curr] = h[maxid]
curr = maxid
else:
break
h[curr] = temp
for i in range(n – 1, 0, -1):
h[0], h[i] = h[i], h[0]
temp = h[0]
curr = 0
while True:
l = 2 * curr + 1
r = l + 1
if l >= i:
break
if r < i and h[r] > h[l]:
maxid = r
else:
maxid = l
if h[maxid] > temp:
h[curr] = h[maxid]
curr = maxid
else:
break
h[curr] = temp
hs(h1)
hs(h2)
i, j = 0, 0
while i < len(h1) and j < len(h2):
if h1[i] < h2[j]:
i += 1
elif h1[i] > h2[j]:
j += 1
else:
res.append(h1[i])
i += 1
j += 1
sys.stdout.write(‘ ‘.join(map(str, res)) + ”)
solve()
Common Elements Using Heap Sort (Alternative)
An alternative approach reads the input line by line and applies the same heap-based sorting and two-pointer intersection.
n, m = map(int, input().split())
h1 = list(map(int, input().split())) if n != 0 else []
h2 = list(map(int, input().split())) if m != 0 else []
res= []
def heapify(heap, i, n):
temp = heap[i]
while True:
l, r = 2*i + 1, 2*i + 2
maxid = i
if l < n and heap[l] > temp:
maxid = l
if r < n and heap[r] > heap[maxid]:
maxid = r
if maxid == i:
break
heap[i] = heap[maxid]
i = maxid
heap[i] = temp
def hs(heap):
n = len(heap)
for i in range(n // 2 – 1, -1, -1):
heapify(heap, i, n)
for i in range(n – 1, 0, -1):
heap[0], heap[i] = heap[i], heap[0]
heapify(heap, 0, i)
hs(h1)
hs(h2)
i, j = 0, 0
while i < len(h1) and j < len(h2):
if h1[i] < h2[j]:
i += 1
elif h1[i] > h2[j]:
j += 1
else:
res.append(h1[i])
i += 1
j += 1
print(‘ ‘.join(map(str, res)))
Minimum Adjacent Difference Pairs
This example uses Python’s built-in heapq module to find the pairs of consecutive values with the smallest difference.
import sys, heapq
data = sys.stdin.read().split()
n = int(data[0])
h = list(map(int, data[1: n + 1]))
heapq.heapify(h)
m = float(‘inf’)
res = []
prev = heapq.heappop(h)
for _ in range(n – 1):
curr = heapq.heappop(h)
d = curr – prev
if d < m:
m = d
res = [f