GingerBear
从Heap到Priority Queue
既然之前说到了Heap，这里有必要聊聊Priority Queue，因为一般Priority Queue使用Heap来实现。
Priority Queue是啥？
Priority Queue（简称PQ）就是根据某个权重排序的一个Queue，换句话说，排好序的数组也可以算是一个PQ，权重就是元素值的大小。PQ有两个操作，第一是Insert操作，要求Insert一个元素到PQ之后，PQ能够自动把它放到合适的位置。第二个是Delete操作，也就是删除并返回最高权重的那个元素。（这不是就是Heap嘛）。
Priority Queue的实现
PQ最简单的实现方法当然就是排序了，把所有元素放到一个list里，每次insert之后都sort一下，delete操作就是最前面那个item摘掉。但这么做的问题是代价太大，每次Insert都要sort，也就是O(n log n)，delete倒是很快O(1)，但考虑到PQ可能经常添加新元素的话，效率明显就太低了。
上面那个方法太笨了，对于排好序的list（使用linked list实现list，为了使中间的插入操作只需要O(1)），insert新元素只需要找到自己的合适位置就好了，用不着每次都重排一次，所以insert操作只需要进行n-i次比较能找到合适位置，即O(n)，delete还是O(1)。
还不够好，如果是排好的数组，为啥不用binary search来找到合适的位置呢？找到位置是O(log n)了，但由于是数组实现，需要移动剩余的元素，所以insert操作还是需要O(n)，如果用linked list来存放元素的话虽然插入操作是O(1)，但由于不能用binary search，找位置还是需要O(n)，delete还是O(1)。
还是不行？heap来了。heap的插入操作终于达到了O(log n)，尽管它的delete是O(log n)，具体实现方法看这里。
另外一种实现方法是Binary Search Tree (BST)，Insert和Delete也是O(log n)，但它较heap的劣势是，heap的初始化操作只需要O(n)，但BST需要O(n log n)。
Priority Queue有一堆牛逼的应用，其中包括有名的Huffman coding， @eric-dango 做过这方面的研究，能不能给大家分享一下？
今天上课讲了一下heap.那天我们简单讨论了一下array【0】能不能放东西。我又想了一下，我认为应该不能，不然从children 回到parents很难实现
建议位置0不要放东西。在面试时要尽量写简单漂亮的代码。你要是把位置0放东西对后面的计算没有益处 On Jan 29, 2014, at 4:06 PM, Neil Ding [email protected] wrote:
@allen6432 我后来也看了一下，标准做法是把第一个空出，但不空也是可以的，就是麻烦一点。
— Reply to this email directly or view it on GitHub.
