数据结构C++实现基本的堆

#pragma once

成都创新互联公司服务项目包括清江浦网站建设、清江浦网站制作、清江浦网页制作以及清江浦网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，清江浦网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到清江浦省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

#include<vector>

#include<queue>

#include<cassert>

#include<iostream>

using namespace std;

//仿函数实现在建堆时确定（大小堆）

template<class T>

struct Greater

{

bool operator()(const T& left,const T& right)

{

return left > right;

}

};

template<class T>

struct Less

{

bool operator()(const T& left, const T& right)

{

return left < right;

}

};

template<class T,class Compare = Less<T>>//默认建小堆

class Heap

{

public:

Heap()

{

}

Heap(const T* array, size_t size)

{

assert(array);

for (size_t i = 0; i < size; ++i)

{

_vec.push_back(array[i]);

}

for (int i = _vec.size() / 2 - 1; i >= 0; --i)

{

_AdjustDown(_vec, i, _vec.size());

}

}

Heap(const vector<T>& vec)

{

_vec.swap(vec);

for (int i = _vec.size() / 2 - 1; i >= 0; --i)

{

_AdjustDown(_vec, i, _vec.size());

}

}

void Push(const T& x)

{

_vec.push_back(x);

if (_vec.size() > 0)

_AdjustUp(_vec, _vec.size() - 1);

}

void Pop()

{

swap(_vec[0], _vec[_vec.size() - 1]);

_vec.pop_back();

_AdjustDown(_vec, 0, _vec.size());

}

const T& GetTop()

{

assert(_vec.size() > 0);

return _vec[0];

}

bool Empty()

{

return _vec.empty();

}

size_t Size()

{

return _vec.size();

}

private:

void _AdjustDown(vector<T>& vec,int root,int size)

{

int left = root * 2 + 1;

while (left < size)

{

if (left+1 < size && Compare()(vec[left+1], vec[left]))

++left;

if (Compare()(vec[left], vec[root]))

{

swap(vec[left], vec[root]);

root = left;

left = root * 2 + 1;

}

else

break;

}

}

void _AdjustUp(vector<T>& vec,int index)

{

int parent = index >> 1;

while (Compare()(vec[index], vec[parent]))

{

swap(vec[index], vec[parent]);

index = parent;

parent = index >> 1;

}

}

protected:

vector<T> _vec;//底层使用vector来实现

};

void test()

{

int arr[] = { 1, 2, 8, 9, 7, 4, 6, 5, 11, 10 };

Heap<int> h(arr, sizeof(arr) / sizeof(arr[0]));

h.Push(0);

h.Pop();

cout << h.GetTop() << endl;

h.Pop();

}

文章标题：数据结构C++实现基本的堆
本文网址：https://www.cdcxhl.com/article20/gihsco.html

成都网站建设公司_创新互联，为您提供定制开发、移动网站建设、响应式网站、全网营销推广、定制网站、外贸网站建设

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联