Heap (large root heap, small root heap)

Updated to 1 day ago

The heap is a special tree structure that can quickly locate the maximum or minimum values. It is the key to implementing heap sorting and priority queues. At the same time, priority queues are mainly used in scenarios such as event processing and task scheduling.

definition

In Python, the heap is divided into a large root heap and a small root heap. They are essentially a completely binary tree, but their node size relationship is different:

Big root heap: For any node i, the value of node i is not less than the value of any child node of it, that is, the value of the parent node is greater than or equal to the value of the child node. It uses an array to implement: counting from zero, for all k , there is heap [k] >= heap [2k+1] and heap [k] >= heap [2k+2]
Small root heap: For any node i, the value of node i is not greater than the value of any child node, that is, the value of the parent node is less than or equal to the value of the child node. It uses an array to implement: counting from zero, and for all k, there is heap [k] <= heap [2k+1] and heap [k] <= heap [2k+2]

Large root heaps and small root heaps are similar in implementation.The only difference is that when inserting, you need to add a symbol (large root heap is negative, small root heap is positive), and when you take out the element, you can add a symbol again.. Using the heapq module, you only need to add a negative sign to turn the large root heap into a small root heap, and then pop the top element of the heap (that is, the smallest element) through the heap function to achieve the maximum element in the heap.

import heapq

# Small root pile
min_heap = []
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 2)
heapq.heappush(min_heap, 3)

# The output is [1, 2, 3]
print(min_heap)

# Big root pile
max_heap = []
for num in [1, 2, 3]:
    heapq.heappush(max_heap, -num) 	# Pay attention to the negative sign!  !  !

# The output result is [-3, -2, -1]
print(max_heap)

# Remove the largest element from the large root heap
print(-heapq.heappop(max_heap))  # Output 3 # Note the negative sign!  !  !

accomplish

In Python, we can use the built-in heapq module to implement heap operations.It implements a small root heap by default. If you need to implement a large heap, you just need to take the opposite number of elements inserted into the heap.

Python's heapq module provides some functions for heap operations. The most commonly used ones are:

heappush(heap, item): Add element item to the heap
heappop(heap): Pop up the smallest element in the heap heap and return, and the heap changes.
heapify(x): Convert list x to heap.
heapreplace(heap, item): Pop up the smallest element in the heap heap and add the element item to the heap.
nlargest(n, iterable, key=None): Returns n elements with the largest value in iterable, and the optional parameter key is used to specify the sorting basis.
nsmallest(n, iterable, key=None): Returns n elements with the smallest value in iterable, and the optional parameter key is used to specify the sorting basis.

application

Heap application: Heap application is very wide, such as in priority queues, sorting, and graph algorithms. In Python, we can use functions from the heapq module to solve these problems. Here are some examples:
(1) Use heap sort

import heapq

nums = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# Convert list to small root heap
heapq.heapify(nums)

# Pop up elements in the heap from small to large
sorted_nums = []
while nums:
    sorted_nums.append(heapq.heappop(nums))

print(sorted_nums)

(2) Use heap to implement priority queue
This is a simple priority queue implementation where each element has a corresponding priority. We can use the push function to add elements to the queue and use the pop function to pop the elements with the highest priority. Note that a _index variable is used here to ensure that elements that are first added to the queue are popped up first when priority is equal.

import heapq

class PriorityQueue:

	# Create an empty list heap and a variable index as the underlying data structure and index value of the priority queue.
    def __init__(self):
        self._heap = []
        self._index = 0
        
	# In the push method, add the element item and priority priority to the heap, and in order to maintain the properties of the small root heap, add the priority priority to the heap in the opposite number (i.e. insert -priority).  At the same time, to ensure that subsequent inserted elements are sorted in the order of insertion, add index to the heap as the second element.  Finally, add the inserted element to the heap as a tuple.
    def push(self, item, priority):
        heapq.heappush(self._heap, (-priority, self._index, item))
        self._index += 1
        
	# In the pop method, pop the heap top element (that is, the element with the highest priority) and return the last element in the tuple (that is, the item).
    def pop(self):
        return heapq.heappop(self._heap)[-1]

(3) Use heap to achieve the minimum spanning tree

import heapq

def prim(graph):
    visited = set()
    edges = []
    start_vertex = next(iter(graph))
    visited.add(start_vertex)

    for neighbor, weight in graph[start_vertex].items():
        heapq.heappush(edges, (weight, start_vertex, neighbor))

    mst = []
    while edges:
        weight, u, v = heapq.heappop(edges)
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            for neighbor, weight in graph[v].items():
                if neighbor not in visited:
                    heapq.heappush(edges, (weight, v, neighbor))

    return mst