transform a list
into a heap
in-place
#import the heapq module
import heapq
L = [9, 3, 10, 7, 5, 2, 4]
heapq.heapify(L)
print(L)
Heaps are data structures that are optimized for finding the minimum(or maximum) element in a collection of elements. This makes them very efficient for implementing priority queues which are data structures that allow connecting multiple elements with varying priorities, and efficiently retrieving the element with the highest priority.
Transform a list into a heap
The heapify()
function, which is a part of the standard library heapq
module, is used to transform a list object into a heap data structure.
heapify(heap)
heap |
The list to be transformed into a heap. |
The heapify()
function essentially rearranges the elements of the list in place in such a way that they satisfies the heap property. After the transformation, the smallest element will always be at the front of the list ( index 0).
Transform a list into a heap
#import the heapq modul
import heapq
L = [5, 1, 7, 2, 9, 6]
heapq.heapify(L)
print(L)
We can then use other functions defined in the heapq
module to perform operations on the heapified list without violating the heap property.
Use heappop
()
to retrieve elements while maintaining the heap property.
#import the heapq modul
import heapq
L = [5, 1, 7, 2, 8, 4, 0, 9, 3, 6]
heapq.heapify(L)
while len(L) > 0:
print(heapq.heappop(L))
In the following example, we use the heappush()
function to insert elements into the heap without violating the heap property.
insert elements into the heap
import heapq
L = [6, 4, 7, 3, 1, 8, 2]
heapq.heapify(L)
heapq.heappush(L, 100)
heapq.heappush(L, 50)
heapq.heappush(L, 20)
heapq.heappush(L, 10)
heapq.heappush(L, 0)
print(L)