数据结构 之 堆（完全二叉树、大根堆、小根堆）

2024-08-22 03:08
文章标签 二叉树 数据结构 完全 小根堆 大根堆

本文主要是介绍数据结构 之 堆（完全二叉树、大根堆、小根堆），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

堆是一种完全二叉树结构，这意味着它具有完全二叉树的性质，其中一点如下所示：

设完全二叉树的一元素编号为i，1 <= I <= n，n为元素总数。有以下关系成立：
1、如果i=1，则该元素为二叉树的根节点，若i>1，则其父节点的编号为(int)(i/2)；
2、如果2*i > n，则该元素无左孩子。否则，其左孩子的编号为2 * i;
3、如果1 + 2*i > n ，则该元素无右孩子，否则，其右孩子的编号为1+2*i

这里写图片描述
之前在看堆结构的内容的时候，误认为需要将树结构引入进来进行堆中元素的管理。但是因为上面的性质使得这一切不在需要树结构。使用数组的方式就能够管理。
大根堆是大根树的一种。大根树是一种父节点值始终大于其子节点的值的结构。根树不是完全二叉树类型的，但是根堆是。
下面以大根堆为例，进行对这种具有一定属性的堆结构的插入、删除、构造和“整理”操作：
插入节点
在插入的时候，首先将数据放置到完全二叉树的下一个子节点上。然后判断其与父节点值得大小，如果父节点的值小，那么将父节点和子节点的值进行交换；交换完成之后，接着判断插入数值所在的节点与其父节点的值大小，如果仍旧是父节点的数值小，则继续交换……直到满足父节点的数值更大或者不存在父节点的情况发生。
以上面的示意图为例，如果我插入的是数值2。那么他本来就满足父节点大的情况，不需要进行任何操作。但是如果插入的是10，则需要将数值8 和数值6都向下降一级，同时，数值10一路升级到最顶点。
这里写图片描述
插入的代码如下所示：

//// 需要在堆底部增加一个元素，然后自底向上进行大小关系的比较和交换位置template<class T>void myHeapArray<T>::push_back(T val){if (0 == (m_back - m_front + 1 + m_len) % m_len)////将要满了，扩容{T* p = new T[(int)(m_len * 1.2 + 1)];if (m_back >= m_front)/////正常模式，正常扩容，仅修改m_len即可{memcpy(p, m_ptr, sizeof(T) * m_len);}else////按照堆的安排方式，是不存在这种情况的，因为数组前面的位置不存在空出来的机会{memcpy(p, &(m_ptr[m_front]), sizeof(T) * (m_len - m_front));memcpy(&(p[m_len - m_front]), m_ptr, m_back);m_front = 0;m_back = (m_back - m_front) % m_len;}delete[] m_ptr;m_ptr = p;m_len = (int)(m_len * 1.2 + 1);}m_ptr[m_back] = val;m_back = m_back + 1;int curNode = m_back - 1;int parNode = (int)((m_front - 1 + curNode) / 2);while (parNode >= m_front)////还没有到达堆顶部{if (m_ptr[curNode] > m_ptr[parNode])////子节点的值比父节点的值大，需要交换{T tmp = m_ptr[curNode];m_ptr[curNode] = m_ptr[parNode];m_ptr[parNode] = tmp;curNode = parNode;parNode = (int)((m_front - 1 + curNode) / 2);}else////// 因为push的操作是在前面都遵循了一定的规范的，所以可以直接跳过{break;}}}

删除操作
删除操作的做法有点奇妙。因为删除操作是删除最上面的顶点，在删除之后，树会被分割成两棵树（如果存在两棵子树），不在便于维护，所以改为将最后的一个子节点移除出去，同时将其数值移动到顶点上面，这样保持了树的结构，还删除了一个顶点。但是，可以预见的是，现在这棵树已经不再满足是大根树的条件。需要对树进行“整理”。方法是从顶点开始，比较节点与子树（存在的话）的值大小，如果子树的数值大，那么就交换两个节点的数值，如果换下去之后的节点的数值仍旧比其子节点的数值小，则继续进行该操作知道满足父节点的数值大于子节点的数值，或者不存在子节点为止。
这里写图片描述
下面贴上从栈顶删除一个元素的代码

    ////从栈顶上删除一个元素//// 需要把堆底的元素挪到堆顶部，然后进行整理template<class T>T myHeapArray<T>::pop_front(void){if(m_back == m_front){throw("NoElmentToPop");}else{T val = m_ptr[m_front];///// 其实没有必要取余数，利用数组进行堆管理不存在back到前面去的情况m_back = (m_len + m_back - 1) % m_len;///// 其实没有必要取余数，利用数组进行堆管理不存在back到前面去的情况///// 把最后一个元素防止到最前面，覆盖掉，表示删除了顶部的元素m_ptr[m_front] = m_ptr[m_back];int curNode = m_front;int childNodeL = 2 * curNode - m_front + 1;int childNodeR = childNodeL + 1;int swapNode;int tmp;while (childNodeL < m_back)//////至少存在一个节点{if (childNodeR < m_back)/// 存在两个子节点{////// 至少存在一个子节点是大于父节点的，必然要进行交换if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode]){if (m_ptr[childNodeL] > m_ptr[childNodeR]){swapNode = childNodeL;}else{swapNode = childNodeR;}}else//// 两个子节点都比父节点小，可以不继续交换了{break;}}else////只存在一个左子节点{if (m_ptr[curNode] < m_ptr[childNodeL])//// 子节点的数值比较大，需要进行交换{swapNode = childNodeL;}else//// 只有一个节点，而且节点大小也满足停止条件{break;}}tmp = m_ptr[swapNode];m_ptr[swapNode] = m_ptr[curNode];m_ptr[curNode] = tmp;//// 更新位置curNode = swapNode;childNodeL = 2 * curNode - m_front + 1;childNodeR = childNodeL + 1;}return(val);}}

整理操作
整理操作是对一个没有大小关系的堆结构进行大小的定位，使堆结构能够具有大根或者小根的特点的操作。
下面的示意图是使用到的一些求节点的表达式：
这里写图片描述
下面是整理部分的代码，其实可以从整理的代码中可以看到，堆（也是完全二叉树，虽然在这里使用的是数组的管理方法，但是仍旧能够体现出树的递归的性质）。这部分的思考感觉在一些边缘条件上面还可以推敲，希望大家能留言多多指导

template<class T>
void myHeapArray<T>::sort(int pos)
{int curNode = pos;int childNodeL = 2 * curNode - m_front + 1;int childNodeR = childNodeL + 1;////// 再次体现树结构的递归特点，虽然这里不是以树的的组织形式，而是数组的形式if (childNodeL < m_back){sort(childNodeL);}if (childNodeR < m_back){sort(childNodeR);}int swapNode;int tmp;while (childNodeL < m_back)//////至少存在一个节点{if (childNodeR < m_back)/// 存在两个子节点{////// 至少存在一个子节点是大于父节点的，必然要进行交换if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode]){if (m_ptr[childNodeL] > m_ptr[childNodeR]){swapNode = childNodeL;}else{swapNode = childNodeR;}}else//// 两个子节点都比父节点小，可以不继续交换了{break;}}else////只存在一个左子节点{if (m_ptr[curNode] < m_ptr[childNodeL])//// 子节点的数值比较大，需要进行交换{swapNode = childNodeL;}else//// 只有一个节点，而且节点大小也满足停止条件{break;}}tmp = m_ptr[swapNode];m_ptr[swapNode] = m_ptr[curNode];m_ptr[curNode] = tmp;//// 更新位置curNode = swapNode;childNodeL = 2 * curNode - m_front + 1;childNodeR = childNodeL + 1;}
}

构造操作
在写完上面的插入操作的时候，构造的操作也就变得简单了。既可以通过对数组逐个执行插入的操作来完成由数组到堆结构的构造，也可以由整理操作来完成堆结构的大小定位。
下面贴上构造中使用的sort函数代码（对一棵树进行整理，使其符合大根堆或小根堆的特点）

    template<class T>void myHeapArray<T>::sort(int pos){int curNode = pos;int childNodeL = 2 * curNode - m_front + 1;int childNodeR = childNodeL + 1;////// 再次体现树结构的递归特点，虽然这里不是以树的的组织形式，而是数组的形式if (childNodeL < m_back){sort(childNodeL);}if (childNodeR < m_back){sort(childNodeR);}int swapNode;int tmp;while (childNodeL < m_back)//////至少存在一个节点{if (childNodeR < m_back)/// 存在两个子节点{////// 至少存在一个子节点是大于父节点的，必然要进行交换if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode]){if (m_ptr[childNodeL] > m_ptr[childNodeR]){swapNode = childNodeL;}else{swapNode = childNodeR;}}else//// 两个子节点都比父节点小，可以不继续交换了{break;}}else////只存在一个左子节点{if (m_ptr[curNode] < m_ptr[childNodeL])//// 子节点的数值比较大，需要进行交换{swapNode = childNodeL;}else//// 只有一个节点，而且节点大小也满足停止条件{break;}}tmp = m_ptr[swapNode];m_ptr[swapNode] = m_ptr[curNode];m_ptr[curNode] = tmp;//// 更新位置curNode = swapNode;childNodeL = 2 * curNode - m_front + 1;childNodeR = childNodeL + 1;}}

下图是使用构造方式获得的大根堆：
这里写图片描述
下面贴上完整的堆结构的模板类代码，以及完整的贴图

    #ifndef _H_MYHEAPARRAY_H#define _H_MYHEAPARRAY_H#include <iostream>template<class T>class myHeapArray;template<class T>class myHeapArray{public:myHeapArray(int len = 64);myHeapArray(const myHeapArray<T>& mqa);myHeapArray(T arr[], int len);~myHeapArray();T pop_front(void);void push_back(T val);int size(void);bool full(void);bool empty(void);T top();myHeapArray<T>& operator=(myHeapArray<T>& mqa);void printAll(void);private:void sort(int pos);private:T* m_ptr;int m_front;int m_back;int m_len;}; D E F I N I T I O N S /template<class T>myHeapArray<T>::myHeapArray(int len = 64){std::cout<<"Constructor by Length"<<std::endl;m_front = 0;m_back = 0;if (len <= 0){len = 16;}m_len = len;m_ptr = new T[m_len];}template<class T>myHeapArray<T>::myHeapArray(const myHeapArray<T>& mqa){std::cout<<"Copy Constructor"<<std::endl;m_front = mqa.m_front;m_back = mqa.m_back;m_len = mqa.m_len;m_ptr = new T[m_len];memcpy(m_ptr, mqa.m_ptr, sizeof(T) * m_len);sort(m_front);}//template<class T>//myHeapArray<T>::myHeapArray(T arr[], int len)//{//  std::cout<<"Constructor by array"<<std::endl;//  m_front = 0;//  m_back = len;//  m_len = (int)(len * 1.2 + 1);//  m_ptr = new T[m_len];//  memcpy(m_ptr, arr, sizeof(T) * len);//  sort(m_front);//}/// 上面和下面的构造函数都可以，结果都符合大根堆的特点template<class T>myHeapArray<T>::myHeapArray(T arr[], int len){std::cout<<"Constructor by array"<<std::endl;m_front = 0;m_back = 0;m_len = (int)(len * 1.2 + 1);m_ptr = new T[m_len];for (int ii = 0; ii < len; ii++){push_back(arr[ii]);}}template<class T>myHeapArray<T>::~myHeapArray(){std::cout<<"Destructor"<<std::endl;if (NULL != m_ptr){delete[] m_ptr;}}从栈顶上删除一个元素 需要把堆底的元素挪到堆顶部，然后进行整理template<class T>T myHeapArray<T>::pop_front(void){if(m_back == m_front){throw("NoElmentToPop");}else{T val = m_ptr[m_front];/ 其实没有必要取余数，利用数组进行堆管理不存在back到前面去的情况m_back = (m_len + m_back - 1) % m_len;/ 其实没有必要取余数，利用数组进行堆管理不存在back到前面去的情况/ 把最后一个元素防止到最前面，覆盖掉，表示删除了顶部的元素m_ptr[m_front] = m_ptr[m_back];int curNode = m_front;int childNodeL = 2 * curNode - m_front + 1;int childNodeR = childNodeL + 1;int swapNode;int tmp;while (childNodeL < m_back)//至少存在一个节点{if (childNodeR < m_back)/// 存在两个子节点{// 至少存在一个子节点是大于父节点的，必然要进行交换if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode]){if (m_ptr[childNodeL] > m_ptr[childNodeR]){swapNode = childNodeL;}else{swapNode = childNodeR;}}else 两个子节点都比父节点小，可以不继续交换了{break;}}else只存在一个左子节点{if (m_ptr[curNode] < m_ptr[childNodeL]) 子节点的数值比较大，需要进行交换{swapNode = childNodeL;}else 只有一个节点，而且节点大小也满足停止条件{break;}}tmp = m_ptr[swapNode];m_ptr[swapNode] = m_ptr[curNode];m_ptr[curNode] = tmp; 更新位置curNode = swapNode;childNodeL = 2 * curNode - m_front + 1;childNodeR = childNodeL + 1;}return(val);}}template<class T>void myHeapArray<T>::sort(int pos){int curNode = pos;int childNodeL = 2 * curNode - m_front + 1;int childNodeR = childNodeL + 1;// 再次体现树结构的递归特点，虽然这里不是以树的的组织形式，而是数组的形式if (childNodeL < m_back){sort(childNodeL);}if (childNodeR < m_back){sort(childNodeR);}int swapNode;int tmp;while (childNodeL < m_back)//至少存在一个节点{if (childNodeR < m_back)/// 存在两个子节点{// 至少存在一个子节点是大于父节点的，必然要进行交换if (m_ptr[childNodeL] > m_ptr[curNode] || m_ptr[childNodeR] > m_ptr[curNode]){if (m_ptr[childNodeL] > m_ptr[childNodeR]){swapNode = childNodeL;}else{swapNode = childNodeR;}}else 两个子节点都比父节点小，可以不继续交换了{break;}}else只存在一个左子节点{if (m_ptr[curNode] < m_ptr[childNodeL]) 子节点的数值比较大，需要进行交换{swapNode = childNodeL;}else 只有一个节点，而且节点大小也满足停止条件{break;}}tmp = m_ptr[swapNode];m_ptr[swapNode] = m_ptr[curNode];m_ptr[curNode] = tmp; 更新位置curNode = swapNode;childNodeL = 2 * curNode - m_front + 1;childNodeR = childNodeL + 1;}} 需要在堆底部增加一个元素，然后自底向上进行大小关系的比较和交换位置template<class T>void myHeapArray<T>::push_back(T val){if (0 == (m_back - m_front + 1 + m_len) % m_len)将要满了，扩容{T* p = new T[(int)(m_len * 1.2 + 1)];if (m_back >= m_front)/正常模式，正常扩容，仅修改m_len即可{memcpy(p, m_ptr, sizeof(T) * m_len);}else按照堆的安排方式，是不存在这种情况的，因为数组前面的位置不存在空出来的机会{memcpy(p, &(m_ptr[m_front]), sizeof(T) * (m_len - m_front));memcpy(&(p[m_len - m_front]), m_ptr, m_back);m_front = 0;m_back = (m_back - m_front) % m_len;}delete[] m_ptr;m_ptr = p;m_len = (int)(m_len * 1.2 + 1);}m_ptr[m_back] = val;m_back = m_back + 1;int curNode = m_back - 1;int parNode = (int)((m_front - 1 + curNode) / 2);while (parNode >= m_front)还没有到达堆顶部{if (m_ptr[curNode] > m_ptr[parNode])子节点的值比父节点的值大，需要交换{T tmp = m_ptr[curNode];m_ptr[curNode] = m_ptr[parNode];m_ptr[parNode] = tmp;curNode = parNode;parNode = (int)((m_front - 1 + curNode) / 2);}else// 因为push的操作是在前面都遵循了一定的规范的，所以可以直接跳过{break;}}}template<class T>int myHeapArray<T>::size(void){return((m_back - m_front + 1 + m_len) % m_len);}template<class T>bool myHeapArray<T>::full(void){return(0 == (m_back - m_front + 1 + m_len) % m_len);}template<class T>bool myHeapArray<T>::empty(void){return(m_back == m_front);}template<class T>T myHeapArray<T>::top(){if (m_front != m_back){return(m_ptr[m_front]);}else{throw("NoElement");}}template<class T>myHeapArray<T>& myHeapArray<T>::operator=(myHeapArray<T>& mqa){std::cout<<"OverLoad Operator"<<std::endl;if (this != &mqa){m_len = mqa.m_len;m_front = mqa.m_front;m_back = mqa.m_back;delete[] m_ptr;m_ptr = new T[m_len];memcpy(m_ptr, mqa.m_ptr, sizeof(T) * m_len);sort(m_front);}return(*this);}template<class T>void myHeapArray<T>::printAll(void){std::cout<<std::endl;for (int ii = m_front; ii < m_back; ii++){std::cout<<"\t"<<m_ptr[ii];}std::cout<<std::endl;}#endif

下图是思考过程中使用的一张插图：
思考过程中使用到的插图---完整版

这篇关于数据结构 之 堆（完全二叉树、大根堆、小根堆）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1095063。

相关文章

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

6.1.数据结构-c/c++堆详解下篇（堆排序，TopK问题）

上篇：6.1.数据结构-c/c++模拟实现堆上篇（向下，上调整算法，建堆，增删数据）-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小)： 2.2 C语言代码（手写堆） 2.3 C++代码（使用优先级队列 priority_queue）
阅读更多...
HDU 2159 二维完全背包

HDU 2159 二维完全背包

FATE 最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能
阅读更多...
zoj 1721 判断2条线段（完全）相交

zoj 1721 判断2条线段（完全）相交

给出起点，终点，与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离，然后最短路。 2点可达条件：没有线段与这2点所构成的线段（完全）相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
阅读更多...
《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

《数据结构（C语言版）第二版》第八章-排序（8.3-交换排序、8.4-选择排序）

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多，算法平均时间性能比直接插入排序差。当初始记录无序，n较大时， 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In
阅读更多...
Regionals 2004 Asia - Beijing Argus 小根堆

Regionals 2004 Asia - Beijing Argus 小根堆

点击打开链接 小根堆 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokeni
阅读更多...
leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
【408数据结构】散列 （哈希）知识点集合复习考点题目

【408数据结构】散列 （哈希）知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独，于是我记下了些许笔记相伴，希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法，它通过散列函数将关键字映射到数组的一个位置，从而实现快速查找。这种方法的时间复杂度平均为(
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
浙大数据结构：树的定义与操作

浙大数据结构：树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2