为什么要使用一个平面列表中堆排序？ [英] Why use a flat list in heapsort?
问题描述
在堆排序，将数据存储在一种叫做堆的。几乎所有我见过的实现使用的数据结构的单位名单的。
In heapsort, the data is stored in something called a "heap". Almost all the implementations I've seen use a flat list for the data structure.
有人能向我解释这是为什么？
为什么不使用嵌套数组或二叉树的例如？是不是优于隐显？
Why not use nested arrays or an instance of a binary Tree? Isn't explicit better than implicit?
是不是因为喜欢穿越的结构，还是其他什么东西执行方面的困难呢？
Is it because of implementation difficulties like traversing the structure, or something else?
推荐答案
如果你想看看堆排序可以在Python中实现再看看没有进一步的比标准库模块 heapq 。 Python有C和Python的堆排序的实现和 heapq 模块定义了Python的人，然后覆盖它们（如果可用）与C的。这意味着你可以阅读和理解Python实现，但得到的C版本的好处，如果你真的使用它。
If you want to see how heapsort can be implemented in Python then look no further than the standard library module heapq. Python has both C and Python implementations of heapsort and the heapq module defines the Python ones then overwrites them (if available) with the C ones. That means you can read and understand the Python implementation but get the benefit of the C version if you actually use it.
使用该模块的一个简单的例子给出了底：
A quick example of using the module is given at the end:
heap = []
data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
for item in data:
heappush(heap, item)
sort = []
while heap:
sort.append(heappop(heap))
print sort
一个堆再由部分排序列表，其中有一个在指数每个元素n在列表中，关系成立的约束psented $ P $的堆[N]＆LT; =堆[ N * 2 + 1]和堆[N]＆LT; =堆[N * 2 + 2] （忽略不存在的元素）。这是一种简单的方法来向下折叠的二进制树来的简单列表，便于存储。
A heap is represented by a partially sorted list which has the constraint that for every element at index n in the list, the relationship holds that heap[n] <= heap[n*2+1] and heap[n] <= heap[n*2+2] (ignoring elements that don't exist). This is a simple way to collapse a binary tree down to a simple list for ease of storage.
heappush（）提出一个新元素到列表中保持了不变， heappop（）删除最小元素。 heapify（somelist）重新排序列表就地满足不变。
heappush() puts a new element into the list maintaining that invariant, heappop() removes the smallest element. heapify(somelist) reorders the list in-place to satisfy the invariant.
当你只想排序的部分名单（给我最小的k个项目），或者你要处理的最小的项目，同时不断接收进入名单的新项目堆排序是非常有用的。后者的一个很好的例子就是一个操作系统任务调度，你保持运行线程的堆优先顺序，并能迅速弹出最高优先级的可运行线程关堆时，你需要安排一个线程来运行。
heapsort is very useful when you want to only sort part of the list (give me the smallest k items), or where you want to process the smallest items while continually receiving new items that go into the list. A good example of the latter would be an operating system task scheduler where you keep a heap of runnable threads in priority order and can quickly pop the highest priority runnable thread off the heap whenever you need to schedule a thread to run.
修改：有几个原因，一个列表/阵列更适合于堆存储不是一个明确的树结构。最明显的是，该明确的树具有更大的存储器开销（无论是涉及每个对象或一个单独的对象内的指针将要分配给在堆中的每个对象），并也较慢的任何时间，你必须在堆内的物体的移动更新多个指针，以孩子和家长可能。
Edit: There are several reasons why a list/array is more appropriate for heap storage than an explicit tree structure. The most obvious ones are that the explicit tree has a greater memory overhead (either involving pointers within each object or a separate object to be allocated for each object in the heap) and is also slower as any time an object moves within the heap you have to update multiple pointers to children and possibly parents.
稍微不太明显的是，你需要能够轻易地得到这是很容易在列表的最后一个元素，但也意味着你还需要存储和更新兄弟指针每个元素。为什么你需要能够获得的最后一个元素容易的是，添加元素的原因，你把它的最后一个元素，然后就其母公司和兄弟（一个O（log n）的操作）或删除重新排序最小的，你只需把目前的最后一个元素在它的位置并重新排列向下。如果你没有为O（1）访问树的最后一个元素，则这两个方法需要一个糟糕的性能损失。
Slightly less obvious is that you need to be able to easily get at the last element which is easy in a list but would mean you also need to store and update sibling pointers on each element. The reason why you need to be able to get at the last element easily is that to add an element you make it the last element and then reorder it with respect to its parent and sibling (an O(log n) operation) or to remove the smallest you simply put the current last element in its place and reorder downwards. If you don't have O(1) access to the final element of the tree then both of these operations take a bad performance hit.
这篇关于为什么要使用一个平面列表中堆排序？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
