Priority queue with dynamically changing priority

background ： Recently, I did an image segmentation task based on graph cut , Each pixel is initially treated as an independent region, Then iterate over the most similar two region A and B A merger , After the merger (A+B) The similarity to other neighbors may be further updated . I consider using a priority queue to store adjacent region The similarity , But here's the problem , General priority queues only support : 1) The team ： Insert elements ; 2) Out of the team ： Get the smallest element . But the reality is , We need dynamic updates region The similarity between . therefore , We need to modify the priority queue , This makes it efficiently support the operation of modifying the elements in the queue .

One 、 Realization way

Priority queues use arrays to organize data , Realized O(logN) The entry and exit operations of . To change the priority of an element , Then you have to find it first . So for a bit of a queue stored in an array , The time complexity of the search is O(N). We are obviously not satisfied with such time complexity .

We noticed that , Priority queues are stored in an array , There are two main internal operations ：ShiftUp and ShiftDown.

ShiftUp： Up float operation , Float the node with lower priority , It is generally used for adjustment after inserting new nodes at the end of the queue

ShiftDown： Sinking operation , Sink the node with higher priority , Used to adjust when the tail of the team changes to the head of the team after leaving the team

Actually , Whether it goes up or down , Elements are interchangeable in a one-dimensional array , As shown in the figure below . Then we can put the data we want to save , Attach one to him key, And then let this key It can be done by associating it with its location .key + data The nodes that make up the queue ,key + position Constitute a map Track node position changes , Fast search .

stay ShiftUp and ShiftDown Of the two operations , In addition to updating the data itself , It is necessary to update the change of data node location in real time , Update it to (key, position)MAP Then you can .

Two 、Show me the code

The comments are written in great detail , I won't explain anymore . Code reference ：https://github.com/kengran/HashHeap/edit/master/main.py, Thanks to the original author , At the same time, I fixed some errors in the original code .

class HashHeap():
    def __init__(self):
        self.A = []  #  Real data is stored in a one-dimensional array , Every node [key, value], value Represents priority 
        self.mapping = {
    }  #  Store the position of each node in a one-dimensional array , Dictionary each item ：[key, position]

    def top(self):  #  Returns the queue header element  min
        if len(self.A) == 0: return None
        return self.A[0]

    def pop(self):  #  The smallest element is out of the team , Adjust the queue at the same time 
        self.A[0], self.A[-1] = self.A[-1], self.A[0]  #  Swap heads and tails 
        key = self.A[0][0]
        del self.mapping[key]  #  Delete the item corresponding to the queue head node in the dictionary 
        self.A.pop()  #  Delete end of team 
        self.siftDown_(0)  #  Put the new team leader shift down

    def siftUp_(self, i):  #  Up float operation , Float the node with lower priority , Used to insert new nodes at the end of the queue   or   Adjustment after manually lowering the priority of some nodes 
        while 0 < i < len(self.A) and self.A[(i - 1) // 2][1] > self.A[i][1]:  #  If the current node priority  <  Parent node priority 
            self.A[(i - 1) // 2], self.A[i] = self.A[i], self.A[(i - 1) // 2]  #  Swap the current node with the parent node 
            self.mapping[self.A[i][0]] = i  #  to update A[i] New location 
            self.mapping[self.A[(i-1)//2][0]] = (i-1)//2 #  to update A[(i-1)/2] New location 
            i = (i - 1) // 2  #  Continue to traverse the parent node 
        return i

    def siftDown_(self, i):  #  Sinking operation , Sink the node with higher priority , Used when the head of the team changes from the tail of the team to the head of the team after leaving the team   or   Adjustment after manually raising the priority of some nodes 
        while 2 * i + 1 < len(self.A):
            min_child, l_child, r_child = i, 2 * i + 1, 2 * i + 2
            #  Determine the node with the lowest priority among the left and right child nodes 
            if l_child < len(self.A) and self.A[l_child][1] < self.A[min_child][1]:
                min_child = l_child
            if r_child < len(self.A) and self.A[r_child][1] < self.A[min_child][1]:
                min_child = r_child
            #  If the current node has a higher priority than the child node , The exchange , And update the mapping
            if min_child > i:
                self.A[i], self.A[min_child] = self.A[min_child], self.A[i]
                self.mapping[self.A[i][0]] = i   #  to update A[i] New location 
                self.mapping[self.A[min_child][0]] = min_child  #  to update A[min_child] New location 
            else:
                break
            i = min_child

        return i

    def push(self, key, val):
        self.A.append([key, val])  #  Add a new node 
        self.mapping[key] = len(self.A) - 1  #  Put the initial position at the end of the team 
        return self.siftUp_(len(self.A) - 1)  #  The final position is determined according to the adjustment 

    def getVal(self, key):  #  Get the priority of a node 
        if key not in self.mapping:
            return -1
        else:
            pos = self.mapping[key]  #  Get the location of this node first 
            return self.A[pos][1]  #  Then get the priority of this node 

    def setVal(self, key, val):  #  Modify existing nodes 
        if key not in self.mapping:
            self.push(key, val)
        else:
            pos = self.mapping[key]
            self.A[pos][1] = val
            pos = self.siftUp_(pos)
            pos = self.siftDown_(pos)

    def remove(self, key):  #  Delete existing nodes 
        if key in self.mapping:
            pos = self.mapping[key]
            self.A[pos], self.A[-1] = self.A[-1], self.A[pos]
            self.mapping[self.A[pos][0]] = pos   #  to update A[pos] New location 
            self.A.pop()
            del self.mapping[key]
            pos = self.siftUp_(pos)
            pos = self.siftDown_(pos)


if __name__ == "__main__":
    priority_queue = HashHeap()
    priority_queue.setVal('a', 4)
    priority_queue.setVal('b', 3)
    priority_queue.setVal('c', 2)

    print(priority_queue.A)
    print(priority_queue.top())

    priority_queue.pop()

    print(priority_queue.A)
    print(priority_queue.top())

The above code has another C++ edition ：https://github.com/mgordon9/HashHeap

Reference material ：

CSDN: A variable priority queue （Mutable Priority Queue） The implementation of the

Stackoverflow: How to update elements within a heap? (priority queue)