首页 > 代码库 > 大-小顶混合堆的实现与应用(a min-max heap)
大-小顶混合堆的实现与应用(a min-max heap)
一般情况下我们使用的堆都是大顶堆或者小顶堆，其能实现在常数时间内获得数组的最大值或者最小值，同时满足在对数时间内删除和插入元素。但是如果要同时实现即能在常数时间内获得最大值和最小值，又能在对数时间内删除和插入元素，通常情况下的堆就不能满足上述要求了。为此介绍一种新的数据结构min-max heap
min-max heap 是一颗完全二叉树，但是二叉树的奇数层存的是max元素，偶数层存的是min元素，也即在以偶数层的某节点为根节的子树中，根节点最大，若在以奇数层为根节点的子树中，根节点最小。根据上述的思想构造出相应的min-max heap。
算法实现：
#include "min_max_heap.h"
#include <iostream>
#include<vector>
using namespace std;
bool min_max_heap::is_min_level(int index)
{
int res = 0;
index = index+1;
while(index>1)
{
res = res + 1;
index = index>>1;
}
if(res % 2 == 0)
return true;
return false;
}
bool min_max_heap::has_child(int index) const
{
int size = data.size();
if(2*index<size-1)
return true;
return false;
}
int min_max_heap::min_child(int index) const
{
int size = data.size();
int res=index*2+1;
if(res<size-1 && data[res]>data[res+1])
res++;
return res;
}
int min_max_heap::max_child(int index) const
{
int size = data.size();
int res = 2*index +1;
if(res<size-1 && data[res]<data[res+1])
res++;
return res;
}
bool min_max_heap::has_grandchild(int index) const
{
int size = data.size();
int k=2*index+1;
if(2*k<size-1)
return true;
return false;
}
int min_max_heap::min_grandchild(int index) const
{
int size = data.size();
int res = 2*index+1;
int left_res = 2*res+1;
if(left_res < size-1 && data[left_res]>data[left_res + 1])
left_res++;
int right_res=-1;
if(has_child(res+1))
right_res = 2*(res+1)+1;
if(right_res == -1)
res = left_res;
else
{
if(right_res < size-1 && data[right_res]>data[right_res + 1])
right_res++;
if(data[left_res] > data[right_res])
res = right_res;
else
res = left_res;
}
return res;
}
int min_max_heap::max_grandchild(int index) const
{
int size = data.size();
int res = 2*index+1;
int left_res = 2*res+1;
if(left_res<size-1 && data[left_res] < data[left_res+1])
left_res++;
int right_res = -1;
if(has_child(res+1))
right_res = 2*(res+1)+1;
if(right_res == -1)
res = left_res;
else
{
if(right_res<size-1 && data[right_res]<data[right_res+1])
right_res++;
if(data[left_res] > data[right_res])
res = left_res;
else
res = right_res;
}
return res;
}
bool min_max_heap::has_grandfather(int index) const
{
if(has_parent(index))
{
int res = parent(index);
if(has_parent(res))
return true;
}
return false;
}
int min_max_heap::grandfather(int index) const
{
int p = parent(index);
return parent(p);
}
bool min_max_heap::has_parent(int index) const
{
if(index == 0)
return false;
int res = (index-1)/2;
if(res >=0)
return true;
return false;
}
int min_max_heap::parent(int index) const
{
int res = (index-1)/2;
return res;
}
min_max_heap::min_max_heap(const int* array, const int n)
{
for(int i=0; i<n; i++)
data.push_back(array[i]);
for(int i=(n-1)/2; i>=0; i--)
{
if(is_min_level(i))
min_shift_down(i);
else
max_shift_down(i);
}
}
min_max_heap::~min_max_heap(){}
void min_max_heap::swap(int i, int j)
{
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
void min_max_heap::min_shift_up(int index)
{
if(!has_parent(index))
return;
else if(!has_grandfather(index))
{
int p = parent(index);
if(data[p] < data[index])
swap(p,index);
return;
}
else
{
int grand = grandfather(index);
if(data[grand] > data[index])
{
swap(index,grand);
min_shift_up(grand);
}
else
{
int p = parent(index);
if(data[p] > data[index])
return;
else
{
swap(p,index);
max_shift_up(p);
}
}
}
}
void min_max_heap::max_shift_up(int index)
{
if(!has_parent(index))
return;
else if(!has_grandfather(index))
{
int p = parent(index);
if(data[p] > data[index])
swap(p,index);
return;
}
else
{
int grand = grandfather(index);
if(data[grand] < data[index])
{
swap(grand,index);
max_shift_up(grand);
}
else
{
int p = parent(index);
if(data[p] < data[index])
return;
else
{
swap(index,p);
min_shift_up(p);
}
}
}
}
void min_max_heap::min_shift_down(int index)
{
if(!has_child(index))
return;
else if(!has_grandchild(index))
{
int c = min_child(index);
if(data[c] <data[index])
swap(c,index);
return;
}
else
{
int c = min_child(index);
if(data[c] < data[index])
{
swap(index,c);
max_shift_down(c);
}
int grand = min_grandchild(index);
if(data[grand] > data[index])
return;
else
{
swap(grand,index);
index = grand;
int p = parent(index);
if(data[p] < data[index])
swap(p,index);
min_shift_down(index);
}
}
}
void min_max_heap::max_shift_down(int index)
{
if(!has_child(index))
return;
else if(!has_grandchild(index))
{
int c = max_child(index);
if(data[c] > data[index])
swap(c,index);
return;
}
else
{
int c = max_child(index);
if(data[c] > data[index])
{
swap(c,index);
min_shift_down(c);
}
int grand = max_grandchild(index);
if(data[grand] < data[index])
return;
else
{
swap(grand,index);
index = grand;
int p = parent(index);
if(data[p] > data[index])
swap(p,index);
max_shift_down(index);
}
}
}
void min_max_heap::insert(int item)
{
data.push_back(item);
int index = data.size()-1;
if(is_min_level(index))
min_shift_up(index);
else
max_shift_up(index);
}
int min_max_heap::delmin()
{
int res = -1;
int n = data.size();
if(n == 0)
return -1;
res = data[0];
swap(0,n-1);
data.pop_back();
min_shift_down(0);
return res;
}
int min_max_heap::delmax()
{
int n = data.size();
int res = -1;
if(n == 0)
return res;
if(n==1)
{
res = data[0];
data.pop_back();
}
else
{
int c = max_child(0);
res = data[c];
swap(c,n-1);
data.pop_back();
max_shift_down(c);
}
return res;
}
int min_max_heap::min()
{
if(data.size()==0)
return -1;
return data[0];
}
int min_max_heap::max()
{
int n = data.size();
if(n==0)
return -1;
if(n==1)
return data[0];
return data[max_child(0)];
}
ostream& operator<<(ostream& os, const min_max_heap& hp)
{
for(unsigned i=0; i<hp.data.size(); i++)
os<<hp.data[i]<<" ";
return os;
}由于存在奇数层和偶数层之分，也即max层和min层之分，因此在堆的“上浮”和“下沉”的过程中要依据节点所在的层次选择不同的“上浮”和“下层”方法
测试代码：
#include <iostream>
#include "min_max_heap.h"
#include <time.h>
#include <stdlib.h>
using namespace std;
int* create_array(const int n);
void main()
{
int n;
cin>>n;
while(n>0)
{
int* a = create_array(n);
cout<<"The array: ";
for(int i=0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
min_max_heap hp(a,n);
cout<<"The min-max heap: "<<hp<<endl;
cout<<"delmax(): ";
for(int i=0; i<n; i++)
cout<<hp.delmax()<<" ";
cout<<endl;
for(int i=0; i<n; i++)
hp.insert(a[i]);
cout<<"The min-max heap: "<<hp<<endl;
cout<<"delmin(): ";
for(int i=0; i<n; i++)
cout<<hp.delmin()<<" ";
cout<<endl;
cin>>n;
}
}
int* create_array(const int n)
{
int* res = new int[n];
for(int i=0; i<n; i++)
res[i] = 0;
for(int i=0; i<n; i++)
{
srand((unsigned)time(0));
while(1)
{
int m=rand()%n;
if(res[m] ==0)
{
res[m] = i;
break;
}
}
}
return res;
}上述代码只是我在学习min-max heap 时使用的测试代码，如有什么不明白的地方欢迎讨论。
大-小顶混合堆的实现与应用(a min-max heap)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。