一般情况下我们使用的堆都是大顶堆或者小顶堆，其能实现在常数时间内获得数组的最大值或者最小值，同时满足在对数时间内删除和插入元素。但是如果要同时实现即能在常数时间内获得最大值和最小值，又能在对数时间内删除和插入元素，通常情况下的堆就不能满足上述要求了。为此介绍一种新的数据结构min-max heap
min-max heap 是一颗完全二叉树，但是二叉树的奇数层存的是max元素，偶数层存的是min元素，也即在以偶数层的某节点为根节的子树中，根节点最大，若在以奇数层为根节点的子树中，根节点最小。根据上述的思想构造出相应的min-max heap。
算法实现：
#include "min_max_heap.h"
#include
#include
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? return true;
?return false;
}
int min_max_heap::min_child(int index) const
{
?int size = data.size();
?int res=index*2+1;
?if(resdata[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? res++;
?return res;
}
bool min_max_heap::has_grandchild(int index) const
{
?int size = data.size();
?int k=2*index+1;
?if(2*k? 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? 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? ?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? 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(gr