Heap Data Structure.

Heap tree-based use case.


In computer science and programming, a Heap is a tree-based data structure (complete binary tree) which is satisfies the heap property:
- Max heap property, where any given node is always greater than its child node and the key of the root node is the largest among all other nodes.
- Min heap property, where any given node is always smaller than the child node and the key of the root node is the smallest among all other nodes.

Heap Data Structure.



The node at the "top" of the heap which has no parents is called the root node.

Heapify is the process of creating a heap data structure from a binary tree, is used to create a Min-Heap or a Max-Heap.
Peek is the process to return the maximum element from Max Heap or minimum element from Min Heap without deleting the node.
Extract-Max/Min is the process to returns the node with maximum/minimum value after removing it from a Max/Min Heap.

In computer science Heap is important for implementing priority queue data structure and for many useful operations like Heap Sort for example. Priority queues are often referred to as heaps queues and Python has a heapq module that implements a priority queue using a binary heap.


Heap queue Python code:



import heapq

print ("Creating original list:")
li = [15, 7, 9, 1, 3, 5, 17]
print (li)

print ("Heapify the list: ")
heapq.heapify(li)
print (list(li))

print ("Push element into heap: ")
heapq.heappush(li,12)
print (list(li))
 
print ("Push element into heap: ")
heapq.heappush(li,11)
print (list(li))

print ("Pop the smallest element from heap: ")
print (heapq.heappop(li))
print (list(li))

print("The 2 largest elements: ")
print(heapq.nlargest(2, li))

print("The 2 smallest elements: ")
print(heapq.nsmallest(2, li))

OUT:
Creating original list:
[15, 7, 9, 1, 3, 5, 17]
Heapify the list:
[1, 3, 5, 7, 15, 9, 17]
Push element into heap:
[1, 3, 5, 7, 15, 9, 17, 12]
Push element into heap:
[1, 3, 5, 7, 15, 9, 17, 12, 11]
Pop the smallest element from heap:
1
[3, 7, 5, 11, 15, 9, 17, 12]
The 2 largest elements:
[17, 15]
The 2 smallest elements:
[3, 5]





See also related topics: