C++数据结构之堆详解

堆的概念

堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象,即是一种顺序储存结构的完全二叉树。

提示:完全二叉树

完全二叉树:对一棵深度为k、有n个结点二叉树编号后,各节点的编号与深度为k的满二叉树相同位置的结点的编号相同,这颗二叉树就被称为完全二叉树。[2]

堆的性质

堆中某个结点的值总是不大于或不小于其父结点的值
堆总是一棵完全二叉树
除了根结点和最后一个左子结点可以没有兄弟结点,其他结点必须有兄弟结点

最大堆最小堆

最大堆:根结点的键值是所有堆结点键值中最大者,且每个结点的值都比其孩子的值大。
最小堆:根结点的键值是所有堆结点键值中最小者,且每个结点的值都比其孩子的值小。

代码

定义

有限数组形式

 	int Heap[1024]; //顺序结构的二叉树

若某结点编号为i,且存在左儿子和右儿子,则他们分别对应

 	Heap[i*2+1]; //左儿子
 	Heap[i*2+2]; //右儿子

其父节点

 	Heap[i/2]; //i的父节点

动态数组形式

在项目开发中,经常以动态数组形式出现,在本文主要对这种形式进行介绍

 	//默认容量
 	#define DEFAULT_CAPCITY 128
 	 
 	typedef struct _Heap
 	{
 	     int *arr; //储存元素的动态数组
 	     int size; //元素个数
 	     int capacity; //当前存储的容量
 	}Heap;

操作

只使用InitHeap()函数进行初始化即可,AdjustDown()与BuildHeap()仅为堆建立时的内部调用

向下调整结点

以创建最大堆为例
将“判断最大子结点是否大于当前父结点”处的>=改为<=即可创建最小堆

 	//向下调整,将当前结点与其子结点调整为最大堆
 	//用static修饰禁止外部调用
 	static void AdjustDown(Heap&  heap, int index)
 	{
 	     int cur = heap.arr[index]; //当前待调整结点
 	     int parent, child;
 	 
 	     /*
 	         判断是否存在子结点大于当前结点。
 	         若不存在,堆是平衡的,则不调整;
 	         若存在,则与最大子结点与之交换,交换后该子节点若还有子结点,则以此方法继续调整。
 	     */
 	     for (parent = index; (parent * 2 + 1) &lt; heap.size; parent = child)
 	     {
 	         child = parent * 2 + 1; //左子结点
 	 
 	         //取两个子结点中最大节点,(child+1)&lt;heap.size防止越界
 	         if (((child + 1) &lt; heap.size & &  (heap.arr[child] &lt; heap.arr[child + 1])))
 	             child++;
 	 
 	         //判断最大子结点是否大于当前父结点
 	         if (cur >= heap.arr[child]) //将此处的>=改成&lt;=可构建最小堆
 	         {
 	             //不大于,不需要调整
 	             break;
 	         }
 	         else
 	         {
 	             //大于,则交换
 	             heap.arr[parent] = heap.arr[child];
 	             heap.arr[child] = cur;
 	         }
 	 
 	     }
 	}

建立堆

 	//建立堆,用static修饰禁止外部调用
 	static void BuildHeap(Heap&  heap)
 	{
 	     int i;
 	     //从倒数第二层开始调整(若只有一层则从该层开始)
 	     for (i = heap.size / 2 - 1; i >= 0; i--)
 	     {
 	         AdjustDown(heap, i);
 	     }
 	}

初始化

 	//初始化堆
 	//参数:被初始化的堆,存放初始数据的数组, 数组大小
 	bool InitHeap(Heap & heap, int *orginal, int size)
 	{
 	     //若容量大于size,则使用默认量,否则为size
 	     int capacity = DEFAULT_CAPCITY>size DEFAULT_CAPCITY:size;
 	
 	     heap.arr = new int[capacity]; //分配内存,类型根据实际需要可修改
 	     if(!heap.arr) return false; //内存分配失败则返回False
 	
 	     heap.capacity = capacity; //容量
 	     heap.size = 0; //元素个数置为0
 	
 	     //若存在原始数组则构建堆
 	     if(size>0)
 	     {
 	         /*
 	         内存拷贝,将orginal的元素拷贝到堆数组arr中
 	         size*sizeof(int)为元素所占内存空间大小
 	         */
 	         memcpy(heap.arr,orginal, size*sizeof(int));
 	         heap.size = size; //调整大小
 	         BuildHeap(heap); //建堆
 	     }
 	
 	     return true;
 	}

打印堆

实际上是一个层序遍历[4]

 	//以树状的形式打印堆
 	void PrintHeapAsTreeStyle(Heap hp)
 	{
 	queue&lt;int> que;
 	     int r = 0;
 	     que.push(r);
 	     queue&lt;int> temp;
 	 
 	     while (!que.empty())
 	     {
 	         r = que.front();
 	         que.pop();
 	 
 	         if (r * 2 + 1 &lt; hp.size) temp.push(r * 2 + 1);
 	         if (r * 2 + 2 &lt; hp.size) temp.push(r * 2 + 2);
 	 
 	         if (que.empty())
 	         {
 	             cout &lt;&lt; hp.arr[r] &lt;&lt; endl;
 	             que = temp;
 	             temp = queue&lt;int>();
 	         }
 	         else
 	             cout &lt;&lt; hp.arr[r] &lt;&lt; " ";
 	 
 	     }
 	}

测试

main函数

 	int main()
 	{
 	     Heap hp;
 	     int vals[] = { 1,2,3,87,93,82,92,86,95 };
 	 
 	     if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0])))
 	     {
 	         fprintf(stderr, "初始化堆失败!\n");
 	         exit(-1);
 	     }
 	 
 	     PrintHeapAsTreeStyle(hp);
 	 
 	     return 0;
 	}

结果

 	95
 	93 92
 	87 1 82 3
 	86 2

完整代码

 	#include &lt;iostream>
 	#include &lt;queue>
 	 
 	using namespace std;
 	 
 	//默认容量
 	#define DEFAULT_CAPCITY 128
 	typedef struct _Heap {
 	     int* arr;
 	     int size;
 	     int capacity;
 	}Heap;
 	 
 	//向下调整,将当前结点与其子结点调整为最大堆
 	static void AdjustDown(Heap&  heap, int index)
 	{
 	     int cur = heap.arr[index]; //当前待调整结点
 	     int parent, child;
 	 
 	     /*
 	         判断是否存在子结点大于当前结点。
 	         若不存在,堆是平衡的,则不调整;
 	         若存在,则与最大子结点与之交换,交换后该子节点若还有子结点,则以此方法继续调整。
 	     */
 	     for (parent = index; (parent * 2 + 1) &lt; heap.size; parent = child)
 	     {
 	         child = parent * 2 + 1; //左子结点
 	 
 	         //取两个子结点中最大节点,(child+1)&lt;heap.size防止越界
 	         if (((child + 1) &lt; heap.size & &  (heap.arr[child] &lt; heap.arr[child + 1])))
 	             child++;
 	 
 	         //判断最大子结点是否大于当前父结点
 	         if (cur >= heap.arr[child]) //将此处的>=改成&lt;=可构建最小堆
 	         {
 	             //不大于,不需要调整
 	             break;
 	         }
 	         else
 	         {
 	             //大于,则交换
 	             heap.arr[parent] = heap.arr[child];
 	             heap.arr[child] = cur;
 	         }
 	 
 	     }
 	 
 	 
 	}
 	 
 	//建立堆,用static修饰禁止外部调用
 	static void BuildHeap(Heap&  heap)
 	{
 	     int i;
 	     //从倒数第二层开始调整(若只有一层则从该层开始)
 	     for (i = heap.size / 2 - 1; i >= 0; i--)
 	     {
 	         AdjustDown(heap, i);
 	     }
 	}
 	 
 	//初始化堆
 	//参数:被初始化的堆,存放初始数据的数组, 数组大小
 	bool InitHeap(Heap&  heap, int* orginal, int size)
 	{
 	     //若容量大于size,则使用默认量,否则为size
 	     int capacity = DEFAULT_CAPCITY > size   DEFAULT_CAPCITY : size;
 	 
 	     heap.arr = new int[capacity]; //分配内存,类型根据实际需要可修改
 	     if (!heap.arr) return false; //内存分配失败则返回False
 	 
 	     heap.capacity = capacity; //容量
 	     heap.size = 0; //元素个数置为0
 	 
 	     //若存在原始数组则构建堆
 	     if (size > 0)
 	     {
 	         /*
 	         内存拷贝,将orginal的元素拷贝到堆数组arr中
 	         size*sizeof(int)为元素所占内存空间大小
 	         */
 	         memcpy(heap.arr, orginal, size * sizeof(int));
 	         heap.size = size; //调整大小
 	         BuildHeap(heap); //建堆
 	     }
 	 
 	     return true;
 	}
 	 
 	//以树状的形式打印堆
 	void PrintHeapAsTreeStyle(Heap hp)
 	{
 	     queue&lt;int> que;
 	     int r = 0;
 	     que.push(r);
 	     queue&lt;int> temp;
 	 
 	     while (!que.empty())
 	     {
 	         r = que.front();
 	         que.pop();
 	 
 	         if (r * 2 + 1 &lt; hp.size) temp.push(r * 2 + 1);
 	         if (r * 2 + 2 &lt; hp.size) temp.push(r * 2 + 2);
 	 
 	         if (que.empty())
 	         {
 	             cout &lt;&lt; hp.arr[r] &lt;&lt; endl;
 	             que = temp;
 	             temp = queue&lt;int>();
 	         }
 	         else
 	             cout &lt;&lt; hp.arr[r] &lt;&lt; " ";
 	 
 	     }
 	 
 	}
 	 
 	int main()
 	{
 	     Heap hp;
 	     int vals[] = { 1,2,3,87,93,82,92,86,95 };
 	 
 	     if (!InitHeap(hp, vals, sizeof(vals) / sizeof(vals[0])))
 	     {
 	         fprintf(stderr, "初始化堆失败!\n");
 	         exit(-1);
 	     }
 	 
 	     PrintHeapAsTreeStyle(hp);
 	 
 	     return 0;
 	}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

标签

发表评论