[Data Structure] Topic 9: Heap

Authored by Tony Feng

Created on March 28th, 2022

Last Modified on March 28th, 2022

Understanding Heaps

Main Concepts

  • Heaps are complete binary trees. Complete binary trees satisfy the following conditions:
    • All levels are filled, except the last.
    • All the nodes are as far left as possible.
  • The root of every subtree should be the greatest or smallest element in the subtree, recursively.
    • Minheap: The root of every subtree is the smallest element.
    • Maxheap: The root of every subtree is the largest element.
  • Heapify: From an array to a heap, the solution is unique and the time complexity is O(N). (Formal Proof)

Applications of Heaps

  • Priority Queues
    • The root of a heap always contains the maximum or the minimum value, based on the heap type.
    • The element with the highest/lowest priority can be retrieved in O(1) time.
  • Statistics
    • If we want the kth smallest or largest element, we can pop the heap k times to retrieve them.
  • Graph Algorithms
    • e.g. Dijkstra’s algorithm, Prim’s algorithm.

Operations

  • Search
    • For the top of heap, it’s O(1)
    • The rest are O(N)
  • Insert - O(log(N))
  • Delete - O(log(N))

Set Implementation in Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import heapq

# Create a minheap
minheap = []
heapq.heapify(minheap) 
# In Python, there is no maxheap. If maxheap is required, 
# try to multiply each element with -1 and then heapify it.
# In the operations, the value should be converted back.

# Add elements
heapq.heappush(minheap, 10)
heapq.heappush(minheap, 8)
heapq.heappush(minheap, 9)
heapq.heappush(minheap, 2)
heapq.heappush(minheap, 1)
heapq.heappush(minheap, 11) # [1,2,9,10,8,11]

# Peek
print(minheap[0])

# Delete
heapq.heappop(minheap)

# Size
len(minheap)

# Iteration
while len(minheap) != 0:
    print(heapq.heappop(minheap))
    

Set Implementation in Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

// Create
PriorityQueue<Integer> minheap = new PriorityQueue<>();
PriorityQueue<Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder());

// Add
minheap.add(2);
maxheap.add(3);

// Peek
int mi = minheap.peek();
int ma = maxheap.peek();  

// Remove the top element
int mi = minheap.poll();
int ma = maxheap.poll(); 

// Get the size of the heap
int lenMin = minheap.size();
int lenMax = maxheap.size();

// Iteration
while (!minheap.isEmpty()) {
    System.out.println(minheap.poll());
}

Reference


MIT License
Last updated on Apr 22, 2022 08:58 EDT
Built with Hugo
Theme Stack designed by Jimmy