常州网站设计湛江公司电话,软件外包公司人数,北京网站设计外包公司价格,wordpress 3清新主题堆的定义
二叉树中的堆使用顺序存储的结构来进行存储这里的堆指代的是一种数据结构
在一个关键码存在的集合中K {K1,K2,K3,....,Kn},把它的所有元素按照完全二叉树的顺序存储方式#xff0c;存储在一个一维数组中#xff0c;如果根结点的元素值大于其左右孩子的值#xf…堆的定义
二叉树中的堆使用顺序存储的结构来进行存储这里的堆指代的是一种数据结构
在一个关键码存在的集合中K {K1,K2,K3,....,Kn},把它的所有元素按照完全二叉树的顺序存储方式存储在一个一维数组中如果根结点的元素值大于其左右孩子的值并且每个子树都满足这种情况其对应的堆我们称为最大堆
堆的相关操作
//Heap.h#pragma once
#includeiostream
#includestdlib.h
#includestdbool.h
using namespace std;#pragma region 定义堆的存储结构
typedef int HeapDataType;
/*定义哨兵*/
#define MAXDATA 0xfffff
typedef struct HNode* heap;
typedef heap MaxHeap;/*MaxHeapHeapHNode 所以MaxHeap是指针类型*/
typedef struct HNode
{HeapDataType* HeadData;/*指针用来指向数据存储的空间*/int sizes;/*当前堆的存储的数据的个数*/int capacity;/*堆所满足的最大的容量*/
};
#pragma endregion
/*堆的创建*/
MaxHeap/*此时实际上返回的是HNode*/ CreatHeap(int MaxSize);
/*堆的销毁*/
void DestoryHeap(MaxHeap M_hp);
/*堆的插入*/
MaxHeap InsertHeap(MaxHeap Mhp, HeapDataType* item);
/*堆的删除*/
MaxHeap DeleteHeap(MaxHeap Mhp);
/*创建最大堆*/
void MoveDown(MaxHeap Mhp, int length);
/*判断堆是否已满*/
bool IsFull(MaxHeap Mhp);
堆的具体实现的CPP程序
#includeHeap.h
/*创建具有MaxSize容量的最大堆*/
MaxHeap/*此时实际上返回的是HNode*/ CreatHeap(int MaxSize)
{MaxHeap Heap NULL;Heap (MaxHeap)malloc(sizeof(HNode));Heap-HeadData (HeapDataType*)malloc(sizeof(HNode)*(MaxSize 1));Heap-capacity MaxSize;Heap-sizes 0;Heap-HeadData[0] MAXDATA;return Heap;
}
#pragma region 销毁最大堆
void DestoryHeap(MaxHeap Mhp)
{if (Mhp NULL){return;}delete[] Mhp-HeadData;Mhp-HeadData NULL;Mhp-capacity 0;Mhp-sizes 0;
}
#pragma endregion
#pragma region 最大堆元素的插入
void SWAP(HeapDataType item_1, HeapDataType item_2)
{HeapDataType tmpstore;tmpstore item_1;item_1 item_2;item_2 item_1;
}
MaxHeap InsertHeap(MaxHeap Mhp, HeapDataType* item)
{if (Mhp NULL || item NULL){return false;/*输入的数据不符合要求*/}MaxHeap tmphp NULL;tmphp Mhp;/*判断是否满了*/if (tmphp-sizes tmphp-capacity){cout 该堆结构存储空间已满 endl;return false;}tmphp-HeadData[tmphp-sizes 1] *item;/*将元素首先放在尾部*/int childPos tmphp-sizes 1;int parentPos childPos / 2;while (tmphp-HeadData[childPos] tmphp-HeadData[parentPos])/*证明插入数据大于根节点的数据*/{SWAP(tmphp-HeadData[childPos], tmphp-HeadData[parentPos]);childPos parentPos;parentPos childPos / 2;}tmphp-sizes;return tmphp;
}
#pragma endregion
#pragma region 最大堆元素的删除
MaxHeap DeleteHeap(MaxHeap Mhp)
{if (Mhp NULL || Mhp-sizes 0){cout 堆为空 endl;return NULL;}MaxHeap tmphp NULL;tmphp Mhp;int parent 1;int child 2 * parent 1;while (childtmphp-sizes){if ((child1tmphp-sizes)/*右孩子存在*/ (tmphp-HeadData[child]tmphp-HeadData[child1]/*选择孩子中的最大一个*/) ){child child 1;/*先找到符合条件的child的位置*/}/*交换*/if (tmphp-HeadData[parent]tmphp-HeadData[child]){SWAP(tmphp-HeadData[parent], tmphp-HeadData[child]);parent child;child 2 * parent 1;}else{break;}}tmphp-sizes--;return tmphp;
}
#pragma endregion
#pragma region 创建最大堆
void MoveDown(MaxHeap Mhp, int length)
{if (Mhp NULL || length 0){cout 输入的堆的元素为空 endl;return;}MaxHeap tmphp NULL;tmphp Mhp;int parent length;int child 2 * length 1;while (child tmphp-sizes)/*防止左孩子出界*/{if ((child1tmphp-sizes) (tmphp-HeadData[child]tmphp-HeadData[child1])){/*右孩子更大*/child child 1;/*将更换的位置调整为右孩子*/}/*判断父结点位置的元素是否比孩子结点的小*/if (tmphp-HeadData[parent]tmphp-HeadData[child]){SWAP(tmphp-HeadData[parent], tmphp-HeadData[child]);parent child;child 2 * parent 1;}else{break;}}
}
MaxHeap CreatMaxHeap(MaxHeap Mhp)
{int length Mhp-sizes/2;MaxHeap tmphp NULL;tmphp Mhp;/*首先找到具有最后一个结点的孩子*/for (length;length0;length--){MoveDown(tmphp, length);}return tmphp;
}
#pragma endregion
#pragma region 判断堆满情况
bool IsFull(MaxHeap Mhp)
{if (Mhp-sizes Mhp-capacity){return true;}return false;
}
#pragma endregion这里需要明确给定一组数据利用大根堆的方式存储具体步骤 首先寻找到具有最后一个顺序存储的叶子结点的父亲结点开始实现自后向前的遍历 遍历的每一个结点都实现基于大根堆的大数据向上移动而小数据向下move down的策略 。所以有了一种针对每个结点都重复一次操作的实现过程。
