铁路网站建设,网站源码下载平台源码,科技文化网站建设方案,一对一软件堆结构与堆排序 文章目录堆结构与堆排序引入堆堆结构所满足的数学特性准备代码----------- 往堆中插入元素----------- 删除堆顶堆排序构建完整代码及测试动态分配版本非动态版本引入堆 二叉树 具有左孩子与右孩子的最普通的二叉树。 满二叉树 特殊的二叉树#xff1a;每个节…堆结构与堆排序 文章目录堆结构与堆排序引入堆堆结构所满足的数学特性准备代码----------- 往堆中插入元素----------- 删除堆顶堆排序构建完整代码及测试动态分配版本非动态版本引入堆 二叉树 具有左孩子与右孩子的最普通的二叉树。 满二叉树 特殊的二叉树每个节点如果有孩子则一定同时具有左孩子与右孩子。
满二叉树的条件
要么有两个孩子要么没有孩子叶子节点在同一层 满二叉树有如下规律 如果层数为n 第n层节点数 一定为 2^(n-1) 整颗树节点数 为 2^n - 1 完全二叉树 能够使得满二叉树 从 下边和右边开始删节点的 二叉树 , 满足从右往左 从下往上删除 和 阅读顺序 相反 满二叉树一定是完全二叉树 完全二叉树不一定是满二叉树 堆 堆是有序的完全二叉树。 父子之间必须有序父大于子或者子大于父同层兄弟之间不用管 父大于子最大堆大顶堆子大于父最小堆小顶堆
堆结构所满足的数学特性 下标关系 150 的 下标为 0 260 的下标为1290的下标为3400的下标为7。共同点都是父节点的左孩子父节点的下标*21左孩子的下标 150的下标为0300的下标为2400的下标为6260的下标为1320的下标为4500的下标为10。共同点都是父节点的右孩子父节点的下标*22右孩子的下标 相反已知400的下标为7则290的下标为3260的下标为1。共同点已知左孩子的下标左孩子下标-1/2得到父节点的下标 已知500的下标为10320的下标为4260 的下标为1。共同点已知右孩子的下标右孩子下标-2/2得到父节点的下标 总结 父亲推孩子 已知父节点下标为N 左孩子下标为2*N 1 右孩子下标为2*N 2 孩子反推父亲 已知左孩子下标为M 父节点下标为 (M-1)/2 已知右孩子下标为M 父节点下标为 (M-2)/2 已知孩子下标为M 父节点下标为 (M-1)/2
准备代码
template class T
class My_Heap
{
private:T* pRoot; //指向堆的指针实际上是一个动态数组int len; //元素个数int MaxLen; //容量
public:My_Heap(){pRoot nullptr;len MaxLen 0;}~My_Heap(){delete[] pRoot;pRoot nullptr;len MaxLen 0;}//往堆中插入元素void insert(const T data);//遍历void travel()const;//删除堆顶T pop();
};----------- 往堆中插入元素
我们采用 小顶堆的方式即保证孩子节点要比父亲节点大。 采用动态内存分配的方法插入一个节点到数组中。 从堆底开始根据下标关系找到对应的父节点.
插入步骤小顶堆
比较插入节点与当前父节点的关系如果比父节点小则当前节点需要上提交换当前节点与父节点的值如果比父节点大则说明不冲突则直接退出即可因为经过以前的处理此情况一定是合法的。继续比较直到不冲突或者到达了根节点为止。
注意我们使用自底向上的方式每次比较当前节点与父节点的关系然后需要将当前节点往上提继续比较和上一层的关系
图例 要点从下往上遍历交换不合适的节点。
templateclass T
inline void My_HeapT::insert(const T data)
{//动态数组//1 像动态数组一样进来if (MaxLen len) {//需要申请//计算需要申请的内存大小 //1 右移一位 等同于除以2MaxLen MaxLen (((MaxLen 1) 1) ? (MaxLen 1) : 1);//1 开内存T* pNew new T[MaxLen];if (pRoot) {//2 pArr指向内存段中数据拷贝到pNew指向内存段memcpy(pNew, pRoot, sizeof(T) * len);//3 释放pArr指向内存段delete[] pRoot;}//4 pArr指向新开内存pRoot pNew;}pRoot[len] data;//循环和父节点比较如果冲突交换不冲突覆盖if (len 1){return;}int CurrentIdx len - 1; //孩子节点int ParentIdx (CurrentIdx - 1) / 2; //父节点T temp;while (1){if (CurrentIdx 0)break; //没有父节点循环结束ParentIdx (CurrentIdx - 1) / 2;if (pRoot[ParentIdx] pRoot[CurrentIdx])break; //不冲突孩子父亲大则停止//否则交换元素temp pRoot[ParentIdx];pRoot[ParentIdx] pRoot[CurrentIdx];pRoot[CurrentIdx] temp;//遍历完一次后接着往上移动开始重新一次比较CurrentIdx ParentIdx;}
}不使用动态内存分配
void InsertData(int val){arr[this-size] val;if (this-size 1) return;int curLen this-size;//当前节点int parentLen curLen 1;//父节点while (true){if (curLen 1) break;//到达根节点退出//比较和父节点的关系比父节点小则交换parentLen curLen 1;if (arr[curLen] arr[parentLen]){break;}swap(arr[curLen], arr[parentLen]);curLen parentLen;}}----------- 删除堆顶
从堆顶开始把最后一个元素覆盖堆顶元素接着根据下标关系找到堆顶的孩子节点比较两个孩子谁是最小孩子如果堆顶比最小孩子节点小则退出小顶堆。否则交换两个节点要保证父小于子。然后顶堆往下移动移动到下一层的父节点比较父子关系。确保在覆盖了原堆顶即删除了原堆顶后整个堆结构仍然是以小堆顶的结构因此要进行重排直到数组下标越界为止。
步骤
最后一个元素覆盖堆顶元素当前节点寻找两个孩子节点的最小的那个并且把那个最小的与当前节点的值作交换当前节点下移继续寻找最小的元素并且作交换直到超过了下界之后停止。
注意如果堆顶元素比左右孩子最小的元素都小则不冲突因此直接结束循环
图例 要点从上往下遍历重排堆结构的父子关系。
template class T
//删除堆顶
T MyHeapT::pop(){if (0 len){cout 堆为空删除失败! endl;return (T)0;}//没法删if (1 len){//只有一个len--;return pRoot[0];}//1 临时保存堆顶元素T temp pRoot[0];//2 最后一个覆盖堆顶元素pRoot[0] pRoot[len - 1];//3 循环 int currentIdx 0;//从堆顶开始int minChildIdx;while (1){//数组结束 if ((currentIdx * 2 1) (len - 1) ||(currentIdx * 2 2) (len - 1)){break;}// 找到最小的孩子 minChildIdx currentIdx * 2 1;//假定左孩子比较小//如果左孩子比右孩子大右孩子最小if (pRoot[minChildIdx] pRoot[minChildIdx 1]) minChildIdx;//比最小孩子还小 循环结束if (pRoot[len-1] pRoot[minChildIdx]) break;//当前位置和最小孩子交换 //子覆盖父//简单交换方式temp1 pRoot[CurrentIdx];pRoot[CurrentIdx] pRoot[MinChildIdx];pRoot[MinChildIdx] temp1;//往下移动currentIdx minChildIdx;}//4 返回len--;return temp;
}不使用动态内存分配
int pop(){/*删除堆顶元素*/if (this-size 1){this-size 0;return arr[1];}//1. 最后一个元素覆盖堆顶元素int temp arr[1];arr[1] arr[this-size];int curLen 1;//当前节点int childLen curLen 1;//孩子节点while (true){//下移超过了边界则退出if (((curLen 1) this-size) || (curLen 1 | 1) this-size){break;}//找到两个孩子中最小的一个childLen curLen 1;//默认最小的是左孩子if (arr[childLen] arr[childLen 1]){childLen 1;//最小的为右孩子}//堆顶比最小的孩子还小则无需交换if (arr[this-size] arr[childLen]) break;//交换当前节点与孩子节点的值swap(arr[childLen], arr[curLen]);curLen childLen;//下移到孩子}this-size--;//最后总的个数要减一个return temp;}堆排序构建
template class T
//直接用数组方式来构建堆
void MyHeapT::initHeap(T* pArr, int size){//开内存maxLen size;len 0;pRoot new T[size];//数据进来pRoot[len] pArr[0];//第一个int currentIdx;int parentIdx;for (int i 1; i size; i){currentIdx len;parentIdx (currentIdx - 1) / 2;//数据先放进来pRoot[currentIdx] pArr[i];while (1){if (currentIdx 0) break;//没有父节点 循环结束parentIdx (currentIdx - 1) / 2;if (pRoot[parentIdx] pRoot[currentIdx]) break;//冲突 父节点覆盖子节点pRoot[currentIdx] pRoot[parentIdx];//往上移currentIdx parentIdx;}//新数据覆盖回来pRoot[currentIdx] pArr[i];//个数增加len;}
}完整代码及测试
动态分配版本 #pragma once
#include iostream
using namespace std;
template class T
class My_Heap
{
private:T* pRoot; //指向堆的指针实际上是一个动态数组int len; //元素个数int MaxLen; //容量
public:My_Heap(){pRoot nullptr;len MaxLen 0;}~My_Heap(){delete[] pRoot;pRoot nullptr;len MaxLen 0;}//往堆中插入元素void insert(const T data);//遍历void travel()const;//删除堆顶T pop();void initHeap(T* pArr, int size);
};templateclass T
inline void My_HeapT::insert(const T data)
{//动态数组//1 像动态数组一样进来if (MaxLen len) {//需要申请//计算需要申请的内存大小 //1 右移一位 等同于除以2MaxLen MaxLen (((MaxLen 1) 1) ? (MaxLen 1) : 1);//1 开内存T* pNew new T[MaxLen];if (pRoot) {//2 pArr指向内存段中数据拷贝到pNew指向内存段memcpy(pNew, pRoot, sizeof(T) * len);//3 释放pArr指向内存段delete[] pRoot;}//4 pArr指向新开内存pRoot pNew;}pRoot[len] data;//循环和父节点比较如果冲突交换不冲突覆盖if (len 1){return;}int CurrentIdx len - 1; //孩子节点int ParentIdx (CurrentIdx - 1) / 2; //父节点T temp;while (1){if (CurrentIdx 0)break; //没有父节点循环结束ParentIdx (CurrentIdx - 1) / 2;if (pRoot[ParentIdx] pRoot[CurrentIdx])break; //不冲突循环继续//效率较低temp pRoot[ParentIdx];pRoot[ParentIdx] pRoot[CurrentIdx];pRoot[CurrentIdx] temp;//往上移动CurrentIdx ParentIdx;}
}templateclass T
inline void My_HeapT::travel() const
{for (int i 0; i len; i){cout pRoot[i] ;}cout endl;
}templateclass T
inline T My_HeapT::pop()
{if (len 0){cout 堆为空!\n;return (T)0;}if (len 1){len--; //只有一个元素return pRoot[0];}//1. 临时保存堆顶元素T temp pRoot[0];T temp1;//2. 最后一个元素覆盖堆顶元素pRoot[0] pRoot[len - 1];//从堆顶开始int CurrentIdx 0;int MinChildIdx;while (1){//越界if ((CurrentIdx * 2 1) (len - 1) ||(CurrentIdx * 2 2) (len - 1)){break;}//找到最小孩子//先假设左孩子比较小MinChildIdx CurrentIdx * 2 1;if (pRoot[MinChildIdx] pRoot[MinChildIdx 1]){MinChildIdx; //右孩子比较小}//如果比最小孩子还小if (pRoot[len-1] pRoot[MinChildIdx])break;//需要交换采用简单交换, 子覆盖父temp1 pRoot[CurrentIdx];pRoot[CurrentIdx] pRoot[MinChildIdx];pRoot[MinChildIdx] temp1;//父节点往下移动CurrentIdx MinChildIdx;}len--;return temp;
}template class T
//直接用数组方式来构建堆
void My_HeapT::initHeap(T* pArr, int size) {//开内存MaxLen size;len 0;pRoot new T[size];//数据进来pRoot[len] pArr[0];//第一个int currentIdx;int parentIdx;for (int i 1; i size; i) {currentIdx len;parentIdx (currentIdx - 1) / 2;//数据先放进来pRoot[currentIdx] pArr[i];while (1) {if (currentIdx 0) break;//没有父节点 循环结束parentIdx (currentIdx - 1) / 2;if (pRoot[parentIdx] pRoot[currentIdx]) break;//冲突 父节点覆盖子节点pRoot[currentIdx] pRoot[parentIdx];//往上移currentIdx parentIdx;}//新数据覆盖回来pRoot[currentIdx] pArr[i];//个数增加len;}
}#include MyHeap.h#define NUM 11
int main()
{int arr[NUM] { 150,260,300,290,320,350,500,400,450,490,500 };My_Heapint a;/*for (int i 0; i NUM; i){a.insert(arr[i]);a.travel();}*/a.initHeap(arr, NUM);a.travel();return 0;
}
非动态版本
P1177 【模板】快速排序 ----排序测试
Ac code
#include iostream
#include cstdlib
#include cstring
#include cstdio
using namespace std;
#define int long long
const int N 1e5 10;
const int CurSize 1e5 10;
struct Tree
{int arr[N];int size;Tree() { memset(arr, 0, sizeof(arr)); size 0; }void InsertData(int val){arr[this-size] val;if (this-size 1) return;int curLen this-size;//当前节点int parentLen curLen 1;//父节点while (true){if (curLen 1) break;//到达根节点退出//比较和父节点的关系比父节点小则交换parentLen curLen 1;if (arr[curLen] arr[parentLen]){break;}swap(arr[curLen], arr[parentLen]);curLen parentLen;}}int pop(){/*删除堆顶元素*/if (this-size 1){this-size 0;return arr[1];}//1. 最后一个元素覆盖堆顶元素int temp arr[1];arr[1] arr[this-size];int curLen 1;//当前节点int childLen curLen 1;//孩子节点while (true){//下移超过了边界则退出if (((curLen 1) this-size) || (curLen 1 | 1) this-size){break;}//找到两个孩子中最小的一个childLen curLen 1;//默认最小的是左孩子if (arr[childLen] arr[childLen 1]){childLen 1;//最小的为右孩子}//堆顶比最小的孩子还小则无需交换if (arr[this-size] arr[childLen]) break;//交换当前节点与孩子节点的值swap(arr[childLen], arr[curLen]);curLen childLen;//下移到孩子}this-size--;//最后总的个数要减一个return temp;}
};
signed main()
{Tree t;int n;cin n;for (int i 1; i n; i){int p;cin p;t.InsertData(p);}while (t.size ! 0){cout t.pop() ;}return 0;
}
