数据结构

Data Structures 数据结构

heep(堆)

堆(heap)又被为优先队列(priority queue),但并不是队列(按先后顺序).堆是按优先级dequeue(出队),enqueue(入队).

“堆”是实现调度器的理想数据结构。(Linux中可以使用nice命令来影响进程的优先级)

堆通常是一个可以被看做一棵完全二叉树(complete binary tree)的数组对象(二叉堆(binary heap)

堆顶的优先级高,堆的主要操作是插入和删除最小元素(元素值本身为优先级键值，小元素享有高优先级)。

1. 新加入的节点加入底部,与父节点比较优先级大小,比父节点小就交换.(percolate_up)

2. 删除根节点后生成两个子树,重构堆(percolate_down).将lasted做为根连接子树

堆是非线性数据结构，相当于一维数组，有两个直接后继。

堆的定义如下：

n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

在程序中，堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作：

1. 事先不知道程序所需对象的数量和大小。

2. 对象太大，不适合使用堆栈分配器。

堆使用运行期间分配给代码和堆栈以外的部分内存。

计算公式
parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

这些公式允许我们不使用指针就可以找到任何一个节点的父节点或者子节点。事情比简单的去掉指针要复杂，但这就是交易：我们节约了空间，但是要进行更多计算。幸好这些计算很快并且只需要O(1)的时间。