我什么时候想使用堆？ [英] When would I want to use a heap?

问题描述

除了优先级队列的明显答案，堆什么时候在我的编程冒险中有用？

Besides the obvious answer of a Priority Queue, when would a heap be useful in my programming adventures?

推荐答案

使用它每当您需要快速访问最大（或最小）的项目时，因为该项目将始终是数组或树根的第一个元素。

Use it whenever you need quick access to the largest (or smallest) item, because that item will always be the first element in the array or at the root of the tree.

然而，阵列的其余部分保持部分未分类。因此，即时访问仅可能达到最大（最小）的项目。插入速度很快，所以它是处理传入事件或数据的一种很好的方法，并且始终可以访问最早/最大的数据。

However, the remainder of the array is kept partially unsorted. Thus, instant access is only possible to the largest (smallest) item. Insertions are fast, so it's a good way to deal with incoming events or data and always have access to the earliest/biggest.

对于优先级队列，调度程序（其中最早的项目是需要的）等...

Useful for priority queues, schedulers (where the earliest item is desired), etc...

堆是一个树，父节点的值大于其任何后代节点的值。

A heap is a tree where a parent node's value is larger than that of any of its descendant nodes.

如果您将一个堆看作一个二进制树，按照深度线性顺序存储，那么首先是根节点（然后是下一个节点的子节点）下一个节点）;那么索引N处的节点的子节点是2N + 1和2N + 2。此属性允许快速访问索引。而且由于通过交换节点来操纵堆，这样可以进行就地排序。

If you think of a heap as a binary tree stored in linear order by depth, with the root node first (then the children of that node next, then the children of those nodes next); then the children of a node at index N are at 2N+1 and 2N+2. This property allows quick access-by-index. And since heaps are manipulated by swapping nodes, this allows for in-place sorting.

这篇关于我什么时候想使用堆？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！