认识算法之数据结构(七)堆

146

堆(HEAP)

1、什么是堆

这次要认识的数据结构是堆结构,在介绍堆结构之前,先看看它是长什么样子的:

堆(Heap)是一种特别的树状数据结构。若是满足以下特性,即可称为堆:“给定堆中任意节点P和C,若P是C的母节点,那么P的值会小于等于(或大于等于)C的值”。若母节点的值恒小于等于子节点的值,此堆称为最小堆;反之,若母节点的值恒大于等于子节点的值,此堆称为最大堆。在堆中最顶端的那一个节点,称作根节点,根节点本身没有母节点。

一般的我们习惯使用最小堆,其规则为最小值被存储在顶端的根节点中,且子节点必须大于母节点,同时每个节点的左子节点也要比右子节点小;当要插入新数据时,往往会放到最下面一行靠左的位置,再进行大小比较排序。母子节点的排列顺序为从上到下,子节点的排列顺序为从左到右

2、堆的基本操作

插入数据

先试试往堆里插入数字11,首先按照我们上面说的,先从最下面寻找空位,所以我们将11插入此处,接着按照最小堆的规则,与母节点的13进行比较后发现,11比13要大,不符合最小堆的规则,因此我们需要交换母子节点的位置。


母节点的11要比根节点的1要大,同时11的子节点13和14都比其大,13又比14要小,所以不再进行交换,这样,一个插入数据的演示操作已完成。

删除数据

删除元素时,我们删除的是堆顶的元素并用堆的最后一个节点填补取走的堆顶元素。但用最后一个元素取代堆顶元素可能会对其结构产生影响,因此我们还需要对堆进行符合结构的调整。演示如下:

简单的代码实现(关键部分)

结果: