algorithm - 二叉堆和优先队列

Question

我是堆、二叉堆的新手，我想了解为什么我们需要使用二叉堆来实现优先级队列。我也明白二叉堆的底层数据结构又是一个数组。

所以我的问题是为什么我们不能使用一个数组，按照降序(对于最大堆)或升序(对于最小堆)排序来表示优先级队列？我在这里可能是错的，但我认为如果以这种方式实现，findMax、findMin、插入和删除等操作的时间复杂度将保持几乎相同。那我们能不能不用排序数组来表示优先级队列呢？

我已经读过这个答案:Heap vs Binary Search Tree (BST)

Answer 1

你可以用一个数组来表示一个优先级队列，但是这样做会损失很多效率。想象一下，你向一个数组中插入了一些东西，它的优先级高于队列中的任何对象。它需要转到索引 0，索引 0 处的对象需要转到索引 1，依此类推。

这是O(n)，但是如果你在一个由二叉树组成的优先级队列的前面插入一个值，你只需要改变lg(n)个节点，使得二叉树在建模优先级队列方面比数组是。

删除元素具有相似的时间复杂度。

如果用数组实现，访问优先级队列的后面是常量时间，但如果用二叉树实现，则为 O(n) 时间，所以这是数组相对于二叉树的显着优势，但优先级队列在一般不需要在很多时候访问优先级最低的元素，因此二叉树通常比数组更有效地表示优先级队列。