Detailed introduction to binary heap in python (code example)

This article brings you a detailed introduction (code example) about the binary heap in python. It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

1. Heap

Data structure Heap is a priority queue. A queue is a first-in-first-out data structure. An important variant of queue is called priority queue. Using the priority queue can add objects in any order, and can find (or possibly remove) the smallest element at any time (possibly while adding objects), which means it is more efficient than Python's min method.
In a priority queue, the logical order of items in the queue is determined by their priority. The highest priority item is at the front of the queue, and the lowest priority item is at the back. Therefore, when you queue items into the priority queue, new items may keep moving to the front.

2. Binary Heap Operation

The basic operations of our binary heap implementation are as follows:

BinaryHeap() creates a new, empty binary heap.
insert(k) Adds a new item to the heap.
findMin() returns the item with the smallest key value and leaves the item in the heap.
delMin() Returns the item with the smallest key value, removing the item from the heap.
If the heap is empty, isEmpty() returns true, otherwise it returns false.
size() returns the number of items in the heap.
buildHeap(list) Builds a new heap from a list of keys.

Note that no matter what order we add items to the heap, the smallest one is removed each time.

To make our heap work efficiently, we will take advantage of the logarithmic nature of binary trees to represent our heap. To guarantee logarithmic performance, we must keep the tree balanced. Balanced Binary Tree There are approximately the same number of nodes in the left and right subtrees of the root. It is an empty tree or the absolute value of the height difference between its left and right subtrees does not exceed 1, and the left and right subtrees have approximately the same number of nodes. The sub-trees are all balanced binary trees. In our heap implementation, we keep the tree balanced by creating a complete binary tree. A complete binary tree is a tree in which the nodes at each level are completely filled, and if the last level is not full, then only some nodes on the right are missing. Figure 1 shows an example of a complete binary tree.
Another interesting property of a complete binary tree is that we can represent it using a single list.

# from pythonds.trees.binheap import BinHeap
class BinHeap:
    def __init__(self):
        self.heapList = [0]
        self.currentSize = 0
    def insert(self,k):
        '''将项附加到列表的末尾，并通过比较新添加的项与其父项，我们可以重新获得堆结构属性。 '''
        self.heapList.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)
    def buildHeap(self, alist):
        '''直接将整个列表生成堆，将总开销控制在O(n)'''
        i = len(alist) // 2
        self.currentSize = len(alist)
        self.heapList = [0] + alist[:]  # 分片法[:]建立一个列表的副本
        while (i > 0):
            self.percDown(i)
           i = i - 1
    def percUp(self,i):
        '''如果新添加的项小于其父项，则我们可以将项与其父项交换。'''
        while i // 2 > 0:    # // 取整除 - 返回商的整数部分（向下取整）
            if self.heapList[i] < self.heapList[i//2]:
               tmp = self.heapList[i // 2]
               self.heapList[i // 2] = self.heapList[i]
               self.heapList[i] = tmp
            i = i // 2
    def percDown(self, i):
        &#39;&#39;&#39;将新的根节点沿着一条路径“下沉”，直到比两个子节点都小。&#39;&#39;&#39;
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapList[i] > self.heapList[mc]:
                tmp = self.heapList[i]
                self.heapList[i] = self.heapList[mc]
                self.heapList[mc] = tmp
            i = mc
    def minChild(self, i):
        &#39;&#39;&#39;在选择下沉路径时，如果新根节点比子节点大，那么选择较小的子节点与之交换。&#39;&#39;&#39;
        if i * 2 + 1 > self.currentSize:
            return i * 2
        else:
            if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
                return i * 2
            else:
                return i * 2 + 1
    def delMin(self):
        &#39;&#39;&#39;移走根节点的元素（最小项）后如何保持堆结构和堆次序&#39;&#39;&#39;
        retval = self.heapList[1]
        self.heapList[1] = self.heapList[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapList.pop()
        self.percDown(1)
        return retval
bh = BinHeap()
bh.buildHeap([9,5,6,2,3])
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

The last part about the binary heap is to find a way to generate a "heap" from an unordered list. The first thing we think of is to insert each element in the unordered list into the heap in turn. For a sorted list, we can use binary search to find the appropriate position, and then insert the key value into the heap at the next position, with a time complexity of O(logn). In addition, inserting an element into the list requires moving some other elements of the list to make room for the new node, and the time complexity is O(n). Therefore, the total cost of using the insert method is O(nlogn). In fact, we can directly generate the entire list into a heap and control the total overhead to O(n). Listing 6 shows the operation of generating a heap.

It seems a bit incredible that a binary heap can be generated with O(n) overhead, so I won’t prove it here. But the key to understanding that a heap can be generated with O(n) overhead is because the logn factor is based on the height of the tree. For many operations in buildHeap, the height of the tree is smaller than logn.

The above is the detailed content of Detailed introduction to binary heap in python (code example). For more information, please follow other related articles on the PHP Chinese website!