1. 概述
堆(也叫优先队列),是一棵完全二叉树,它的特点是父节点的值大于(小于)两个子节点的值(分别称为大顶堆和小顶堆)。它常用于管理算法执行过程中的信息,应用场景包括堆排序,优先队列等。
2. 堆的基本操作
堆是一棵完全二叉树,高度为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当前的元素数目
下面给出其主要