年底 网站备案,西安网站建设哪里好,免费企业在线,广告设计公司经营范围有哪些堆#xff1a;是一种数组对象#xff0c;它可以被看成是一种二叉树结构。
我们把堆的二叉树存储方式分为两种#xff1a;即大堆和小堆。那么问题来了#xff0c;什么大堆#xff1f;什么是小堆#xff1f;
大堆#xff1a;让每个父节点的值都大于孩子节点的值。
小堆…堆是一种数组对象它可以被看成是一种二叉树结构。
我们把堆的二叉树存储方式分为两种即大堆和小堆。那么问题来了什么大堆什么是小堆
大堆让每个父节点的值都大于孩子节点的值。
小堆让每个父节点的值都小于孩子节点的值。 说完概念后就来考虑一下如何来实现大堆和小堆吧。第一步肯定得有一个堆吧所以我们首先得建堆这是毋庸置疑的。由于堆实际上就是一个二叉树结构所以先将数压进栈中然后通过向下调整来建大堆。
第一例堆的实现
具体实现代码如下 #pragma once
#includevector
#includeiostream
#includeassert.h
using namespace std;
//仿函数用于下面的父节点与子节点的比较
templateclass T
struct Less
{bool operator()(const T left,const T right){return (left right);}};templateclass T
struct Greater
{bool operator()(const T left,const T right){return (left right);}};templateclass T,class Compare GreaterT
class Heap
{
public:
span stylewhite-space:pre /span//建堆Heap(const T* a,size_t size){assert(a);for(size_t i 0; i size; i){_a.push_back(a[i]);}for(size_t i (_a.size()-2)/2; i 0; i--){AdjustDown(i);}}void push(const T x){_a.push_back(x);AdjustUp(_a.size()-1);}void pop(){assert(!_a.empty());swap(_a[0],_a[_a.size()-1]);_a.pop_back();AdjustDown(0);}bool Empty(){return _a.empty();}size_t Size(){return _a.size();}void print(){for(size_t i 0; i _a.size(); i){cout_a[i] ;}coutendl;}
protected:
span stylewhite-space:pre /span//向下调整void AdjustDown(size_t parent){size_t child parent*21;Compare com;while(child _a.size()){if(child1 _a.size() com(_a[child1],_a[child])){child;}if(com(_a[child],_a[parent])) //孩子节点大于父节点{swap(_a[child],_a[parent]);parent child;child parent*21;}else{break;}}}span stylewhite-space:pre /span//向上调整void AdjustUp(size_t child){size_t parent (child-1)/2;Compare com;while(child 0){if(com(_a[child],_a[parent])) //父节点小于孩子节点{swap(_a[child],_a[parent]);child parent;parent (child-1)/2;}else{break;}}}
protected:vectorT _a;
};
void testHeap()
{int a[] {10,11, 13, 12, 16, 18, 15, 17, 14, 19};Heapint,Greaterint hp(a,sizeof(a)/sizeof(a[0]));hp.push(2);hp.print();
}第二例
同样我们也可以实现堆排序
如图实现方式 1 2 3 ...
依此向下调整的方式进行排序。 void AdjustDown(int a[],int n, int parent){int child parent*21;while(child n){if(child1 n a[child1] a[child]){child;}if(a[child] a[parent]){swap(a[child],a[parent]);parent child;child parent*21;}else{break;}}}void HeapSort(int a[],size_t n){assert(a);for(int i (n-2)/2; i 0; --i){AdjustDown(a,n,i);}for(int i 0; i n; i){ swap(a[0],a[n-1-i]); //交换堆顶元素和最后一个元素AdjustDown(a,n-1-i,0); //将最后一个元素固定向下调整前n-i-1个}}void print(int a[],size_t size){for(size_t i 0; i size;i){couta[i] ;}coutendl;}void TestHeapSort()
{int a[] {2,1,4,5,0,6,3,7,8,9};HeapSort(a, sizeof(a)/sizeof(a[0]));print(a,sizeof(a)/sizeof(a[0]));
} 堆的实现及堆排序就说到这里啦。。堆排序将会在后期排序那部分再与大家见面哦。到时候会与其他排序一起比较包括它的时间复杂度和空间复杂度以及各个排序算法的优缺点。今天的就说到这里啦~~
