在二叉树中,我们用两种方法表示二叉树,一个是链表,一个是数组,但是数组比较适用于满二叉树或者完全二叉树。
堆数据结构是一种数组对象,它可以被视为一棵完全二叉树结构。
堆结构的二叉树存储有两种方法:
最大堆:每个父节点的都大于孩子节点。
最小堆:每个父节点的都小于孩子节点。
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
template<class T>
class Heap
{
public:
Heap()//无参类型的构造函数
{}
Heap(T *a, size_t size)//有参类型的构造函数
{
assert(a);
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
//建堆,用 向下调整 算法
//对于一个完全二叉树,其结点的父子关系与数组的下标的关系:
//左子下标= 父结点下标*2+1
//右子下标=父结点下标*2+2
for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒数第一个非叶子结点(最后一个元素一定是非叶子结点的子节点)
{
_AdjustDown(j);
}
/*
在第一次写时定义了j为size_t类型,由于j不管怎么运算都是无符号类型所以
j>=0并没有起到限制的作用,导致了死循环
*/
}
public:
void Push(const T &x)//在最后加入一个节点
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);//向上调整,传入最后一个元素下标(调整x的位置)
}
void Pop()//把最大的删掉(根)
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);//把根节点和最后一个节点交换
_a.pop_back();//删掉最后一个节点
_AdjustDown(0);//向下调整
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i]<<" ";
}
cout << endl;
}
size_t size()
{
return _a.size();
}
bool empty()
{
return _a.empty();
}
protected:
void _AdjustDown(size_t parent)//时间复杂度O(log2(N))
{
size_t child = parent * 2 + 1; //找到其左孩子
while (child < _a.size())
{
if ((child + 1) < _a.size() && _a[child] < _a[child + 1])//若左孩子小于右孩子(且必须结点下标不超过范围)
{
++child;//指向大的
}
if (_a[child]>_a[parent])//若孩子大于父,则把大的放在父结点上
{
swap(_a[child], _a[parent]);
parent = child;//父和子调整后要继续向下调整交换后的子节点
child = parent * 2 + 1;//现在这个调整后的节点的子节点
}
else
break;
}
}
void _AdjustUp(size_t child)//时间复杂度O(log2(N))
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_a[child] > _a[parent])
{
swap(_a[child], _a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
private:
vector<T> _a;
};
测试函数
void test()
{
int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
Heap<int> h2(a, 10);
h2.Push(3);
h2.Push(4);
h2.Print();
h2.Push(100);
h2.Print();
h2.Pop();
h2.Print();
h2.Pop();
h2.Print();
}
int main()
{
test();
getchar();
return 0;
}
上面实现了最大堆,最小堆方法同最大堆,但是再在类中重新一遍则会使程序的可维护性降低,所以我们用仿函数来实现。
仿函数
仿函数就是使一个类使用看上去像一个函数,其实现就是类中实现一个operator().这个类就有了类似函数的行为。
struct
Free
{
void
operator()(
void
*ptr)
{
free
( ptr);
}
};
void
Testsharedptr()
{
int
*p1=(
int
*)
malloc
(
sizeof
(
int
)*10);
shared_ptr<
int
>sp1(p1,Free());
//在使用完后自动释放p1
}
用仿函数实现最大堆与最小堆
template<class T>
struct Less
{
bool operator()(const T&left, const T&right)
{
return left < right;
}
};
template<class T>
struct Greater
{
bool operator()(const T&left, const T&right)
{
return left>right;
}
};
template<class T,class compare=Greater<T>>
class Heap
{
public:
Heap()//无参类型的构造函数
{}
Heap(T *a, size_t size)//有参类型的构造函数
{
assert(a);
for (size_t i = 0; i < size; i++)
{
_a.push_back(a[i]);
}
//建堆,用 向下调整 算法
//对于一个完全二叉树,其结点的父子关系与数组的下标的关系:
//左子下标= 父结点下标*2+1
//右子下标=父结点下标*2+2
for (int j = (_a.size() - 2) / 2; j >= 0; j--)//找到倒数第一个非叶子结点(最后一个元素一定是非叶子结点的子节点)
{
_AdjustDown(j);
}
}
public:
void Push(const T &x)//在最后加入一个节点
{
_a.push_back(x);
_AdjustUp(_a.size() - 1);//向上调整,传入最后一个元素下标(调整x的位置)
}
void Pop()//把最大的删掉(根)
{
assert(!_a.empty());
swap(_a[0], _a[_a.size() - 1]);//把根节点和最后一个节点交换
_a.pop_back();//删掉最后一个节点
_AdjustDown(0);//向下调整
}
void Print()
{
for (size_t i = 0; i < _a.size(); i++)
{
cout << _a[i]<<" ";
}
cout << endl;
}
size_t size()
{
return _a.size();
}
bool empty()
{
return _a.empty();
}
protected:
void _AdjustDown(size_t parent)//时间复杂度O(log2(N))
{
size_t child = parent * 2 + 1; //找到其左孩子
compare com;
while (child < _a.size())
{
if ((child + 1) < _a.size() && com(_a[child+1],_a[child]))
{
++child;
}
if (com(_a[child],_a[parent]))//
{
swap(_a[child], _a[parent]);
parent = child;//父和子调整后要继续向下调整交换后的子节点
child = parent * 2 + 1;//现在这个调整后的节点的子节点
}
else
break;
}
}
void _AdjustUp(size_t child)//时间复杂度O(log2(N))
{
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;
}
}
private:
vector<T> _a;
};
这样就实现了最大堆与最小堆,通过仿函数,程序的可维护性好于在类中写一个最大堆写法和最小堆写法。
测试
void test1()
{
int a[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
int b[10] = { 5, 10, 34, 24, 2, 4, 17, 23, 12, 9 };
Heap<int,Less<int>> h2(a, 10);//最小堆
h2.Push(3);
h2.Push(4);
h2.Print();
h2.Push(100);
h2.Print();
h2.Pop();
h2.Print();
h2.Pop();
h2.Print();
Heap<int>h3(b);//最大堆
h3.Push(3);
h3.Push(4);
h3.Print();
h3.Push(100);
h3.Print();
h3.Pop();
h3.Print();
h3.Pop();
h3.Print();
}
堆的应用:
1.堆排序
分析:由于在大堆或者小堆排完后,只能保证每个小树为大堆或者小堆,故还需要进行排序才能使数组元素完全依次排列。
所以我们先用大堆排列后,使堆顶元素为大元素,再依次将堆顶元素和未交换的最后一个元素交换,交换完成后再将除了大的元素之外的元素进行交换
/******************************
堆排序
尽建立一个大堆,每次把堆顶的元素和最后一个还未交换的元素交换
*/
void AdjustDown(int *a, int parent, int size)
{
int child = parent * 2 + 1;
while (child < size)
{
if (a[child]<a[child + 1]&&child+1<size)
{
child++;
}
if (a[child] > a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int *a, int n)
{
assert(a);
for (int i = (n - 2) / 2; i >= 0; i--)
{
AdjustDown(a,i,n);//大堆向下调整
}
for (int i = 0; i < n; i++)
{
swap(a[n - 1 - i],a[0]);
AdjustDown(a, 0, n - 1 - i);
}
}
2.求N个元素中前K个最大的数
分析:建立一个小堆存放前K个元素,小堆的堆顶元素为前K个中最小的值,剩下N-K个数中依次和堆顶元素相比较,若大于堆顶元素,入堆,每入堆一个元素再小堆排序一次,使堆顶元素总为这K个元素的最小值;若小于堆顶元素,则继续下一个数比较。当N-K个元素全比较完,堆中这K个元素就是最大的前K个数。
/*
从N个数中找到K个最大的数
建立一个小堆,大小为K,每次从第N-K的数据中取出一个和堆顶元素比较
*/
const int N = 1000000;
const int K = 100;
void AdjustDown(int *a, int parent, int size)
{
int child = parent * 2 + 1;
while (child <size)
{
if (child+1<size&&a[child] > a[child + 1])
{
child++;
}
if (a[child] < a[parent])
{
swap(a[child], a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void GetTopK(int *a)
{
assert(K < N);
int top[100];
for (size_t i = 0; i < 100; i++)
{
top[i] = a[i];
}
//建一个小堆,向下调整
for (int i = (K - 2) / 2; i>=0; i--)
{
AdjustDown(top, i, K);
}
//从剩下的N-K的数据中拿数据和堆顶元素比较,若小于堆顶元素,则入堆
for (size_t j = K; j < N ; j++)
{
if (a[j]<top[0])
{
top[0] = a[j];
AdjustDown(top, 0, K);
}
}
}
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。