Binary heaps are a common data structure that is used in algorithms and data organization. These heaps are binary trees that fulfill certain properties.
There are two types of binary heaps:
The primary use of binary heaps is in implementing priority queues, which are very useful in algorithms such as Dijkstra’s, Prim’s etc. They also make effective sorting methods, like heapsort.
Now, let's see how we can create a binary heap using Python. Python’s heapq module provides functions for creating min-heap and manipulating it.
Let's demonstrate how to push elements into and pop elements from the heap.
import heapq H = [3,5,1,4,6,7,8,9,2,0] heapq.heapify(H) # create heap print("Initial heap: ", H) # Adding elements to the heap heapq.heappush(H, -5) # push -5 print("After pushing an element: ", H) # Removing elements from the heap print("Popped item: ", heapq.heappop(H)) print("Heap after popping an element: ", H)
The program first creates a heap using the heapify() function. We then push a new element '-5' to this heap. Next, an element is popped from the heap using the heappop() function, which always pops the smallest element.
To create a max-heap, we will initialize the data in our list as negative. This way, the element with the highest value will be considered the smallest because it will have the highest negative equivalent.
import heapq H = [3,5,1,4,6,7,8,9,2,0] H_neg = [-1*i for i in H] # convert list elements to negative heapq.heapify(H_neg) # create heap # Adding elements to the heap heapq.heappush(H_neg, -50) # push -50 print("Max-Heap: ", [-1*i for i in H_neg]) # convert back to positive for display # Removing elements from the heap print("Popped item: ", -1*heapq.heappop(H_neg)) # pop and convert to positive
Binary heaps are a simple and efficient way to implement priority queues and are also extensively used in sorting algorithm. In the next post, we'll talk about sorting arrays using heap sort algorithm. Stay tuned!