堆的定义与实现

系列文章目录

前言

一、堆的定义

结构基础：堆是基于完全二叉树的逻辑结构，用数组来物理实现。

核心性质：堆可分为大堆和小堆。
其中，大堆要求每个子树的父节点>=左右子节点。
小堆要求每个子树的父节点 <= 左右子节点。

//堆用C实现typedefintHPDataType;typedefstructHeap{HPDataType*_a;//堆元素的存放数组int_size;//有效元素个数int_capacity;//容量}Heap;

二、堆的实现

为什么堆可以用数组来实现？

因为数组可以实现快速的随机访问，操作更加简单。再加上完全二叉树不会浪费很多数组的空间。

1.大/小堆的构建

（以小堆为例）
为了让最小的数在堆顶，其余的小数都在其子树的父亲节点。
要用到“向下调整”的算法。来调整根节点和两子树的关系，是根保持为最小。

当parent = n, 左 child = 2 * n + 1, 右child = 2 * n + 2 基于数组实现的索引规律

//参数分别为 堆中元素(数组)，元素总个数，需要向下调整的父亲节点voidAdjustdowm(HPDataType*a,intn,introot){intparent=root;intchild=2*parent+1;//先假设左孩子while(child<n)//结束条件：孩子节点不能大于总数{if(child<n&&a[child]>a[child+1]){child++;//右孩子小,使child走到右孩子}//如果孩子节点小于父亲节点if(a[child]<a[parent]){swap(&a[child],&a[parent]);parent=child;child=parent*2+1;}else{break;}}}

但向下调整的前提是单前节点的左右子树都是（小）堆，才能保证拿上来的是最小值。
所以要从最后一个节点的父亲节点开始向下调整，由下到上。

当孩子child = n时，parent = (n-1) /2 最后一个孩子是n-1, 得出最后一个父亲是(n-1-1)/2

//构建堆——以小堆为例for(inti=(n-1-1)/2;i>=0;i--)//从最后一个节点的父亲节点开始，从下往上才能保证左右子树都是小堆{AdjustDown(hp->_a,hp->_size,i);}

2.堆的增删查

如何在堆中增加一个数，而不破坏小堆的形式？
先把数据加在末尾，再使用向上调整算法，使数据到合适的地方。

//向上调整---（以小堆为例）AdjustUp(HPDataType*a,intn,intchild){intparent=(child-1)/2;while(child>0)//当child = 0时，才算调整完{if(a[child]<a[parent]){swap(&a[child],&a[parent]);child=parent;parent=(child-1)/2;}else{break;}}}

增加一个元素

// 堆的插入voidHeapPush(Heap*hp,HPDataType x){//插入时只能先在末尾插入，再调整到堆中合适的地方if(hp->_size==hp->_capacity){hp->_capacity*=2;HPDataType*tmp=(HPDataType*)realloc(hp->_a,sizeof(HPDataType)*hp->_capacity);if(tmp!=NULL){hp->_a=tmp;}else{printf("扩容失败");}}hp->_a[hp->_size++]=x;//需要将插入值向上调整AdjustUp(hp->_a,hp->_size,hp->_size-1);}

删堆顶的数据，是先将堆顶与数组最后一个元素交换，再删除最后一个元素，将新元素向下调整。
因为最后一个元素方面删除。

// 堆的删除——（肯定删的是堆顶的数据）voidHeapPop(Heap*hp){intend=hp->_size-1;if(end<0){return;}else{swap(&hp->_a[0],&hp->_a[end]);hp->_size--;AdjustDown(hp->_a,hp->_size,0);}}