数据结构:堆
堆
1.堆是什么?
2.堆的特性。
3.堆的操作原理
①堆的插入原理
②堆的删除原理
堆
1.堆是什么?
堆是特殊的队列,不同于普通队列,从堆中取出元素是依照元素的优先级大小,而不是元素进入队列的先后顺序,也可以称堆为“优先队列”。
2.堆的特性。
特性①:用数组表示完全二叉树。
堆最常用完全二叉树来表示,因为高为h的完全二叉树有2h-1到2h-1个节点,且节点分布十分规律,也正因如此,可以用数组来实现堆的存储。
如何用数组表示完全二叉树:
根节点存放在数组起始处,为方便子节点找到父节点,起始处下标为1
找寻父节点:某节点下标为 i ,其父节点下标就为 i / 2。
找寻子节点:某节点下标为 i ,其左、右子节点下标分别为 2i ,2i+1。
特性②:部分有序性
任意节点元素的值与其子节点元素的值相关,相关性的不同就决定了两种不同的基本堆:最大堆 和 最小堆。
最大堆:任意节点的值大于或等于其子节点的值,根节点最大。
最小堆:任意节点的值小于或等于其子节点的值,根节点最小。
最大堆( a ),最小堆( b ) 示例:
3.堆的操作原理
(以最大堆为例)
①堆的插入原理
向最大堆插入新元素后,需要保证的是:
—堆依旧是一颗完全二叉树;
—堆中各节点与其子节点的关系依旧符合最大堆性质。
首先,在数组末尾插入新元素,若新节点值 <= 父节点值,说明位于正确位置。
在数组末尾插入新元素时,若新节点值 > 父节点值,需要交换位置,直到比父节点小或没有父节点(抵达根节点),才是抵达正确位置。
②堆的删除原理
删除元素实际上就是取出根节点的最大值元素,再删除一个节点。删除元素后,需要保证的是:
—堆依旧是一颗完全二叉树;
—堆中各节点与其子节点的关系依旧符合最大堆性质。
首先,将根节点(最大值元素)与最后一个节点交换位置,删除最后一个节点,实现取出最大值元素的操作,再删除节点的操作。
(实际上删除的节点元素在数组中依旧存在,但是代表最大堆所含节点数的MaxHeap会减去1,代表删除了最后一个节点)
完成删除操作后,需要在根节点的左、右子结点中取较大的一个与根节点做比较,根节点小于子节点则与其交换位置。
交换后,继续让此节点重复进行比较,直到此节点的值大于>=子节点值或节点成为叶子节点(不存在子节点)就停止。