Introduction to Heap Data Structure Python
Heap data structure in python implements priority queues, an effective tool that provides solutions for complex data-related problems. In its implementation, Heap uses a binary tree structure in which the data is stored hierarchically in nodes, and each node can have a maximum of two child nodes.
Priority queues are used in several applications, such as determining the shortest possible routes, log files merging, scheduling jobs, and many other optimization problems. Heap data structure has options for providing maximum priority for the highest number as well as the lowest number in the data series it handles, but heapq module as part of Python standard library support the lowest level only.
A brief on Heaps / Priority queues
Heaps provide concrete data models, and Priority queues are abstract in nature. In the binary data tree, it may violate heap property whenever data is inserted or deleted. The entire data structure undergoes suitable restructuring, and thus the anomaly gets fixed.
Though the data is logically stored in binary structures, it is represented as a list for easy operations.
How does Heap Data Structure Work in Python?
Heap stores the data in a binary tree structure to optimize search operations and get results faster. It stores the lowest value in its node structure and the rest of the data in parent and child nodes. The structure gets adjusted whenever new data is added and removed.
heapq module
heapq module in Python has several functions in it to manage several data operations that may be required in maintaining data structure and retaining its heap properties.
|
Sl |
Function |
Description |
| 1 | Heapify | With an empty heap, users can insert Data elements into a heap, which is a tedious and time-consuming activity. Heapq provides a facility for users can upload data elements into heap en masse in one go. The minimum value in the data will be stored in the root node as the first data element, thus preserving the property of the heap. Otherwise, Heapify does not do any sorting of data elements, but it retains the order as it is. |
| 2 | Heappush | This function adds a new data element into the heap without disturbing its property. The data is added, and the heap property is validated, and the heap is restructured if it is not in order. If the added data is the smallest in a heap, it is added as a root, and the rest of the data is adjusted suitably. |
| 3 | Heappop | Heappop removes the lowest valued data element from the heap and automatically moves the next lowest element into the root node. The characteristics of the heap are retained post-execution of this step. |
| 4 | Heappushpop | This function executes the combined activity of Heappush first and then Heappop later. It adds the new data element, removes the existing smallest element from the heap, and puts the next smallest in the root. This command takes a shorter time to execute than the sum of two individual operations. |
| 5 | Heapreplace | It is the combination of Heappop operation first and Heappush later. It deletes the smallest item from the list first and adds the new item in a heap. It is executed faster than the combined operations of delete and add. |
| 6 | Nlargest | This function culls out the largest numbers from the heap. Users can specify the number of largest numbers and the key value as a selection criterion. Data elements meeting the selection criterion will only be considered for picking out the largest numbers. |
| 7 | Nsmallest | The Nsmallest function returns the smallest valued data element from the heap. The user has the option to choose n number of smallest items as well as the selection of elements based on key values. |
Examples of Heap Data Structure Python
Below are the different examples of Heap Data Structure Python:
1. Heappush()
This code creates a dummy heap first and then pushes numbers in a heap. It also prints the elements in the list one by one and as a list.
Code:
# Code to explain Heappush
import heapq as q1 # import heapq module
heaptest = []# Define a dummy list
q1.heappush(heaptest,5) # Push values
q1.heappush(heaptest,4)
q1.heappush(heaptest,112)
q1.heappush(heaptest,45)
q1.heappush(heaptest,22)
print ("Heap list - Individual values ") # Print values one by one
for element in heaptest:
print(element)
print (" ")
print ("Heap List") # print as a list
print (heaptest)Output:
When another number is pushed into a heap.
q1.heappush(heaptest,2)
print ("Heap List (After addition)")
print (heaptest)Output:
2. Heapify()
This function converts a raw data elements list into heap format.
Code:
# Code to explain Heapify
import heapq as q1 # import heapq module
heaptest = [82,26,34,23,7,4,92] # Raw list
print ("Original List") # printing raw list
print (" ")
print (heaptest)
print ("")
q1.heapify(heaptest) # conversion into heap
print ("heap list") # printing heap
print (" ")
print (heaptest)Output:
3. Heappop()
This Code removes the first data element (lowest value) from the heap
Code:
# Code to explain Heappop
import heapq as q1 # import heapq module
heaptest = [82,26,34,23,7,4,92]
q1.heapify(heaptest)
print ("")
print ("heap list before pop up ")
print (" ")
print (heaptest)
q1.heappop(heaptest)
print ("")
print ("heap list after first pop up ")
print (" ")
print (heaptest)
q1.heappop(heaptest)
print ("")
print ("heap list after second pop up ")
print (" ")
print (heaptest)Output:
4. Heappushpop()
This function adds the new item(Push) and removes the first item (pop)
Code:
# Code to explain Heappushpop
import heapq as q1 # import heapq module
heaptest = [82,26,34,23,7,4,92]
q1.heapify(heaptest)
print ("")
print ("heap list before")
print (" ")
print (heaptest)
q1.heappushpop(heaptest,2) # added and removed
print ("")
print ("heap list after first pushpop up ")
print (" ")
print (heaptest)
q1.heappushpop(heaptest,5)
print ("")
print ("heap list after second pushpop up ")
print (" ")
print (heaptest)
q1.heappushpop(heaptest,86)
print ("")
print ("heap list after third pushpop up ")
print (" ")
print (heaptest)Output:
5. Heapreplace()
Removal of the lowest element takes place first (popup), and the addition (push) takes place.
Code:
# Code to explain Heapreplace
import heapq as q1 # import heapq module
heaptest = [82,26,34,23,7,4,92]
q1.heapify(heaptest)
print ("")
print ("heap list before")
print (" ")
print (heaptest)
q1.heapreplace(heaptest,2) # Existing lowest value removed
print ("") # New value (lowest) added
print ("heap list after first replace ")
print (" ")
print (heaptest)
q1.heapreplace(heaptest,5)
print ("")
print ("heap list after second replace ")
print (" ")
print (heaptest)
q1.heapreplace(heaptest,86)
print ("")
print ("heap list after third replace ")
print (" ")
print (heaptest)Output:
6. Largest and smallest numbers in a heap
Code:
# Code to explain largest and smallest numbers
import heapq as q1 # import heapq module
heaptest = [82,26,34,23,7,4,92]
q1.heapify(heaptest)
print ("")
print ("Full heap list")
print (" ")
print (heaptest)
print ("")
print ("Two Highest numbers")
print (q1.nlargest(2,heaptest))
print ("")
print ("Two lowest numbers")
print (q1.nsmallest(2,heaptest))Output:
Conclusion
Using heapq data can be added or removed from heap and heap maintains binary tree effectively and quickly brings out the search results.