Heap data structure is mainly used to represent a priority queue. In Python, it is available using the heapq module. The property of this data structure in Python is that each time the smallest heap element is popped(min-heap). Whenever elements are pushed or popped, heap structure is maintained. The heap[0] element also returns the smallest element each time (min heap)
# importing "heapq" to implement heap queue
import heapq
# initializing list
li = [5, 7, 9, 1, 3]
# using heapify to convert list into heap
heapq.heapify(li)
# printing created heap
print ("The created heap is : ",(list(li)))
The created heap is
The created heap is : [1, 3, 9, 7, 5]
There are three rules that determine the relationship between the element at the index k and its surrounding elements:
2*k + 1.2*k + 2.(k - 1) // 2.Note:The // symbol is the integer division operator. It always rounds down to an integer.
Since the root of the tree is the first element, you don’t need a dedicated function to read the smallest element nondestructively. The first element, a[0], will always be the smallest element.
To pop the smallest element while preserving the heap property, the Python heapq module defines heappop().
Here’s how to use heappop() to pop an element:
>>> import heapq
>>> a = [1, 2, 3, 5, 6, 8, 7]
>>> heapq.heappop(a)
1
>>> a
[2, 5, 3, 7, 6, 8]
The Python heapq module also includes heappush() for pushing an element to the heap while preserving the heap property.
The following example shows pushing a value to a heap:
>>> import heapq
>>> a = [2, 5, 3, 7, 6, 8]
>>> heapq.heappush(a, 4)
>>> a
[2, 5, 3, 7, 6, 8, 4]
>>> heapq.heappop(a)
2
>>> heapq.heappop(a)
3
>>> heapq.heappop(a)
4
After pushing 4 to the heap, you pop three elements from it. Since 2 and 3 were already in the heap and are smaller than 4, they’re popped first.
The Python heapq module also defines two more operations:
heapreplace() is equivalent to heappop() followed by heappush().heappushpop() is equivalent to heappush() followed by heappop().In Python, the heapq module provides a heap queue algorithm. By default, heapq creates a min heap, which is a binary heap where the smallest element is always at the root. However, if you want to create a max heap (where the largest element is at the root), you can use a simple trick by negating the values when inserting into the heap.
import heapq
class MaxHeap:
def __init__(self):
self.heap = []
def push(self, value):
heapq.heappush(self.heap, -value)
def pop(self):
return -heapq.heappop(self.heap)
A heap, as an implementation of a priority queue, is a good tool for solving problems that involve extremes, like the most or least of a given metric.
There are other words that indicate a heap might be useful:
By using a list of tuples where the first element is the key you want to heapify by.
import heapq
# get frequencies
def count_frequency(lst):
frequency_dict = {}
for element in lst:
if element in frequency_dict:
frequency_dict[element] += 1
else:
frequency_dict[element] = 1
result = [(key, value) for key, value in frequency_dict.items()]
return result
# Your original list
frequency_list = [(1, 3), (2, 2), (3, 9), (4, 8)]
# Convert the list of tuples to a list of tuples with the second element as the key
heapified_list = [(x[1], x) for x in original_list]
# Convert the list to a heap
heapq.heapify(heapified_list)
# Extract the original tuples from the heapified list
result_list = [x[1] for x in heapified_list]
# The original list is now heapified based on the second value of each tuple
print(result_list)
In this example, the key parameter is used to specify a custom function that extracts the second element of each tuple to determine the heap order. The heapify function then rearranges the list to satisfy the heap property based on the specified key.
This can be useful for problems o type top k most frequent or k less frequent