使用最大堆数据结构的优先级队列

Question

我正在 Python 中使用最大堆数据结构实现优先级队列。我使用了几个名称，这些名称将与它们相关联的数字作为它们的优先级（9 是最高的，1 是最低的）。我面临的问题是，当我从优先级队列中取出一个项目时，它不会使具有最高优先级的项目出列。我认为这意味着我的入队有问题，它没有根据项目的优先级将项目插入到堆中的正确位置。如果有人能帮我解决这个问题，将不胜感激。

我的优先队列代码：

from Heap import Heap

class priorityQ(object):
    def __init__(self):
        self.PQ = Heap()

    def enqueue(self, priority, item):
        self.PQ.insert((priority, item))

    def dequeue(self):
        if self.PQ.size() == 0:
            raise ValueError("Empty Queue")
        return self.PQ.delete_max()

    def first(self):
        return self.PQ.get_max()

    def size(self):
        return self.PQ.size()

def main():
    myHeap = priorityQ()
    print(myHeap.size())
    myHeap.enqueue(8, "Kaneda")
    myHeap.enqueue(6, "Masaru")
    myHeap.enqueue(9, "Akira")
    myHeap.enqueue(4, " Kei")
    myHeap.enqueue(5, "Takashi")
    myHeap.enqueue(2, "Shikishima")
    myHeap.enqueue(3, "Kiyoko")
    myHeap.enqueue(1, "Yamagata")
    myHeap.enqueue(7, "Tetsuo")
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())
    myHeap.dequeue()
    print(myHeap.first())
    print(myHeap.size())

在我运行代码和调用 main 之后输出：

0
(9, 'Akira')
9
(7, 'Tetsuo')
8
(5, 'Takashi')
7
(4, 'Kei')
6
(3, 'Kiyoko')
5
(2, 'Shikishima')
4
(1, 'Yamagata')
3
(1, 'Yamagata')
2
(1, 'Yamagata')
1
None
0

最大堆代码（教材提供）：

# Heap.py
class Heap(object):

    #------------------------------------------------------------

    def __init__(self, items=None):

        '''post: a heap is created with specified items'''

        self.heap = [None]
        if items is None:
            self.heap_size = 0
        else:
            self.heap += items
            self.heap_size = len(items)
            self._build_heap()

    #------------------------------------------------------------

    def size(self):

        '''post: returns number of items in the heap'''

        return self.heap_size

    #------------------------------------------------------------

    def _heapify(self, position):

        '''pre: items from 0 to position - 1 satisfy the heap property
        post: heap property is satisfied for the entire heap'''

        item = self.heap[position]
        while position * 2 <= self.heap_size:
            child = position * 2
            # if right child, determine maximum of two children
            if (child != self.heap_size and 
                self.heap[child+1] > self.heap[child]):
                child += 1
            if self.heap[child] > item:
                self.heap[position] = self.heap[child]
                position = child
            else:
                break
        self.heap[position] = item

    #------------------------------------------------------------

    def delete_max(self):

        '''pre: heap property is satisfied
        post: maximum element in heap is removed and returned'''

        if self.heap_size > 0:
            max_item = self.heap[1]
            self.heap[1] = self.heap[self.heap_size]
            self.heap_size -= 1
            self.heap.pop()
            if self.heap_size > 0:
                self._heapify(1)
            return max_item

    def get_max(self):
        if self.heap_size > 0:
            max_item = self.heap[1]
            self.heap[1] = self.heap[self.heap_size]
            if self.heap_size > 0:
                self._heapify(1)
            return max_item

    #------------------------------------------------------------

    def insert(self, item):

        '''pre: heap property is satisfied
        post: item is inserted in proper location in heap'''

        self.heap_size += 1
        # extend the length of the list
        self.heap.append(None)
        position = self.heap_size
        parent = position // 2
        while parent > 0 and self.heap[parent] < item:
            # move item down
            self.heap[position] = self.heap[parent]
            position = parent
            parent = position // 2
        # put new item in correct spot
        self.heap[position] = item

    #------------------------------------------------------------

    def _build_heap(self):

        '''pre: self.heap has values in 1 to self.heap_size 
        post: heap property is satisfied for entire heap'''

        # 1 through self.heap_size
        for i in range(self.heap_size // 2, 0, -1): # stops at 1
            self._heapify(i)

    #------------------------------------------------------------

    def heapsort(self):

        '''pre: heap property is satisfied
        post: items are sorted in self.heap[1:self.sorted_size]'''

        sorted_size = self.heap_size
        for i in range(0, sorted_size - 1):
            # Since delete_max calls pop to remove an item, we need 
            # to append a dummy value to avoid an illegal index.
            self.heap.append(None)
            item = self.delete_max()
            self.heap[sorted_size - i] = item

Answer 1

你的问题似乎在你的队列中。

def enqueue(self, item, priority):
        self.PQ.insert(item)

根本没有使用优先级参数。相反，您的堆正在使用字符串比较。

这是您的堆在任何出列之前的状态：

[None, 'Yamagata', 'Tetsuo', 'Shikishima', 'Takashi', 'Masaru', 'Akira', 'Kiyoko', 'Kei', 'Kaneda']

使用最大堆数据结构的优先级队列

Priority Queue using a Max-Heap Data Structure

python

heap

insert

priority-queue

max-heap