二叉堆和优先队列
Binary Heap and Priority Queues
我是堆、二叉堆的新手，我想了解为什么我们需要使用二叉堆来实现优先级队列。我也明白二叉堆的底层数据结构又是一个数组。
所以我的问题是为什么我们不能使用按降序（对于最大堆）或升序（对于最小堆）排序的数组来表示优先级队列？我在这里可能是错的，但我认为如果以这种方式实现，findMax、findMin、插入和删除等操作的时间复杂度将保持几乎相同。那我们可不可以不用排序数组来表示优先级队列呢？
我已经读过这个答案：Heap vs Binary Search Tree (BST)
你可以用一个数组来表示一个优先级队列，但是这样做会损失很多效率。想象一下，你向一个数组中插入了一些东西，它的优先级高于队列中的任何对象。它需要转到索引 0，索引 0 处的对象需要转到索引 1，依此类推。
这是O(n)，但是如果在二叉树组成的优先级队列的最前面插入一个值，只需要改变lg(n)个节点，二叉树在优先级建模方面会好很多队列比数组多。
删除元素具有相似的时间复杂度。
如果用数组实现，访问优先级队列的后面是常数时间，但是如果用二叉树实现，则为O(n)时间，所以这是数组相对于二叉树的一个显着优势，但是优先级队列通常不需要在很多时候访问优先级最低的元素，因此二叉树通常比数组更有效地表示优先级队列。
两者各有优缺点：
树更灵活，如果它们是平衡的，则具有更好的性能，具有 worst-case 对数搜索、插入和删除。所有这些好处都是有代价的。在树、列表和图形中，每个节点都需要额外的 space
对于指针和每个节点放置在随机位置，这会导致内存开销
数组中的所有元素在内存中都是连续的，这意味着读取它们时的延迟更低。如果删除和插入不会经常发生，请使用排序数组
我是堆、二叉堆的新手，我想了解为什么我们需要使用二叉堆来实现优先级队列。我也明白二叉堆的底层数据结构又是一个数组。
所以我的问题是为什么我们不能使用按降序（对于最大堆）或升序（对于最小堆）排序的数组来表示优先级队列？我在这里可能是错的，但我认为如果以这种方式实现，findMax、findMin、插入和删除等操作的时间复杂度将保持几乎相同。那我们可不可以不用排序数组来表示优先级队列呢？
我已经读过这个答案：Heap vs Binary Search Tree (BST)
你可以用一个数组来表示一个优先级队列，但是这样做会损失很多效率。想象一下，你向一个数组中插入了一些东西，它的优先级高于队列中的任何对象。它需要转到索引 0，索引 0 处的对象需要转到索引 1，依此类推。
这是O(n)，但是如果在二叉树组成的优先级队列的最前面插入一个值，只需要改变lg(n)个节点，二叉树在优先级建模方面会好很多队列比数组多。
删除元素具有相似的时间复杂度。
如果用数组实现，访问优先级队列的后面是常数时间，但是如果用二叉树实现，则为O(n)时间，所以这是数组相对于二叉树的一个显着优势，但是优先级队列通常不需要在很多时候访问优先级最低的元素，因此二叉树通常比数组更有效地表示优先级队列。
两者各有优缺点：
树更灵活，如果它们是平衡的，则具有更好的性能，具有 worst-case 对数搜索、插入和删除。所有这些好处都是有代价的。在树、列表和图形中，每个节点都需要额外的 space 对于指针和每个节点放置在随机位置，这会导致内存开销
数组中的所有元素在内存中都是连续的，这意味着读取它们时的延迟更低。如果删除和插入不会经常发生，请使用排序数组