理论篇-数据结构之堆

2017-05-28

堆的底层实现一般是数组，堆可以看做是一棵近似完全二叉树。堆中的节点从上到下，从左到右，依次填充(只有最底层不会被填充满)。树的根节点是A[1]，给定任意节点，我们可以很容易得计算它的父节点，左孩子节点和右孩子节点的指针。

heap

给定任意节点i，它的父节点、左孩子节点和右孩子节点的计算方法如下:

1
2
3

parent: i/2
left: 2i
right: 2i+1

有两种类型的二叉堆: 大顶堆和小顶堆。

大顶堆的性质如下: 除了跟节点之外，其他任何节点的值都要小于或等于父节点的值。

小顶堆的性质如下: 除了根节点之外，其他任何节点的值都要大于或等于父节点的值。

堆的主要应用: 1. 堆排序 2. 实现优先级队列。

堆排序对于从海量数据中获取最小或最大的k个数特别有效。

思路: 首先建立一个能容纳k个元素的堆。然后遍历海量数据，将合适的值加入到堆中。最后进行一次堆排序，最后，得到已经有序的k个元素。

优先级队列一般用于任务的管理。比如最大优先级队列用来管理进程的切换，最小优先级队列用来管理超时任务。