5、堆

什么是堆

一种特殊的队列，队列中元素出栈的顺序是按照元素的优先权大小，而不是元素入队的先后顺序。

堆的特性：

• 必须是完全二叉树
• 用数组实现
• 任一结点的值是其子树所有结点的最大值或最小值
  • 最大值时，称为“最大堆”，也称大顶堆；
  • 最小值时，称为“最小堆”，也称小顶堆。

可以看到，对于堆（Heap）这种数据结构，从根节点到任意结点路径上所有的结点都是有序的。

堆的基本操作

堆是一棵完全二叉树，高度为O（lg n），其基本操作至多与树的高度成正比。在介绍堆的基本操作之前，先介绍几个基本术语：

A：用于表示堆的数组，下标从1开始，一直到n
PARENT(t)：节点t的父节点，即floor(t/2)
RIGHT(t)：节点t的左孩子节点，即:2*t
LEFT(t)：节点t的右孩子节点，即:2*t+1
HEAP_SIZE(A)：堆A当前的元素数目

保持堆的性质 Heapify(A,n,t)

该操作主要用于维持堆的基本性质。假定以RIGHT(t)和LEFT(t)为根的子树都已经是堆，然后调整以t为根的子树，使之成为堆。

建堆 BuildHeap(A,n)

操作主要是将数组A转化成一个大顶堆。思想是，先找到堆的最后一个非叶子节点（即为第n/2个节点），然后从该节点开始，从后往前逐个调整每个子树，使之称为堆，最终整个数组便是一个堆。子数组A[(n/2)+1..n]中的元素都是树中的叶子，因此都可以看作是只含有一个元素的堆。