优先级队列是一种队列，其中每个元素都有一个与之关联的密钥，并且队列根据这些密钥返回元素，这与以先到先服务为基础的传统队列不同。
因此，最大优先级队列首先返回具有最大密钥的元素，而最小优先级队列首先返回具有最小密钥的元素。
优先级队列用于许多算法，如霍夫曼码，普里姆算法等。它还用于计算机的调度过程等。
堆非常适合实现优先级队列，因为树的根最大和最小元素分别用于最大堆和最小堆。我们对最大优先级队列使用max-heap，对最小优先级队列使用min-heap。
我们希望优先队列中有4个操作：
1. 插入 →在队列中插入新元素。
2. 最大/最小 →分别从最大优先级队列和最小优先级队列中获取最大和最小元素。
3. 提取最大值/最小值 →分别从最大优先级队列和最小优先级队列中删除并返回最大和最小元素。
4. 增加/减少键 →增加或减少队列中任何元素的键。
优先级队列根据元素的键以特定顺序存储其数据。因此，插入新数据必须按照指定的顺序放在一个位置。这就是插入操作的作用。
优先级队列的整个点是根据数据的密钥获取数据，最大值/最小值和提取最大值/最小值对我们这样做。
通过这些操作，我们满足了对优先级队列的大部分需求，即将数据插入队列并从队列中获取数据。但是我们也可能面临需要更改元素键的情况，因此使用“增加/减少”键来执行此操作。
让我们学习编写这些操作来编写优先级队列。
下面给出的伪代码用于最大优先级队列。但是，本文末尾给出了最高优先级和最低优先级队列的C，Java和Python完整代码。
如前所述，我们将使用堆作为优先级队列。
最大/最小
我们知道优先级队列的最大（或最小）元素位于最大堆（或最小堆）的根。所以，我们只需要在堆的根处返回元素。
最大值（A） 返回A [1]
从数组返回一个元素是一个恒定的时间进程，所以它是一个 Θ（1） 处理。
提取最大/最小值
这就像队列的弹出一样，我们返回元素并将其从堆中删除。因此，我们必须返回并删除堆的根。首先，我们将root的值存储在一个变量中，以便稍后从函数中返回它，然后我们只使root等于堆的最后一个元素。现在root等于堆的最后一个元素，我们通过将堆的大小减少1来轻松删除最后一个元素。
这样做，我们扰乱了root的堆属性，但是我们没有触及它的任何子节点，所以它们仍然是堆。因此，我们可以在根上调用Heapify以使树再次成为堆。
EXTRACT-MAXIMUM（A） max = A [1] // stroing最大值 A [1] = A [heap_size] //使root等于最后一个元素 heap_size = heap_size-1 //删除最后一个元素 MAX-HEAPIFY（A，1）// root不遵循max-heap属性 return max //返回最大值
除了Heapify操作之外，所有步骤都是恒定的时间进程，它将采取O （lgn） 时间，因此提取最大/最小将采取 O （lgn） 时间。
增加/减少键
每当我们更改元素的键时，它必须根据新键改变其位置以进入正确的顺序。如果堆是最大堆并且我们正在减少密钥，那么我们只需要检查密钥是否变得小于其任何子项。如果新密钥小于其任何子代，则它违反了堆属性，因此我们将在其上调用Heapify。
在增加max-heap中元素的键的情况下，我们可能使它大于其父键的键，从而违反了heap属性。在这种情况下，我们交换父节点和节点的值，直到节点的父节点变得大于节点本身为止。
在最小队列的情况下，我们完全与上述步骤相反。
INCREASE-KEY(A, i, key) A[i] = key // changing key while i > 1 and A[Parent(i) < A[i] // if parent is less than A[i], we will swap. swap (A[i], A[Parent(i)]) i = Parent(i) DECREASE-KEY(A, i, key) A[i] = key // changing key MAX-HEAPIFY(A, i)
它类似于Heapify操作。我们不是沿着树下行，而是向上行驶，所以它也将采取行动LG?
在最坏的情况下的时间，即，它是一个 O （lgn） 操作。
插入
插入操作根据其键以正确的顺序插入新元素。我们只是在堆的最后一个处插入一个新元素，并将堆大小增加1.因为它是最后一个元素，所以我们首先在min-heap的情况下给出一个非常大的值（无穷大），并且值非常小（-inf）在max-heap的情况下。然后我们只需使用Increase / Decrease键操作来更改元素的键。
INSERT（A，key） heap_size = heap_size + 1 //将堆大小增加1 [heap_size] = -infinity //使最后一个元素非常少 INCREASE-KEY（A，heap_size，key）//最后一个元素的chaning键
所有步骤都是恒定的时间步骤，除了增加/减少键。所以它也需要O （lgn） 时间。
欢迎大家在评论区留言讨论，整理不易，请大家多多收藏、关注。您的关注是对我最大的支持。