and,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] ? ?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? os<?return os;
}
由于存在奇数层和偶数层之分，也即max层和min层之分，因此在堆的“上浮”和“下沉”的过程中要依据节点所在的层次选择不同的“上浮”和“下层”方法
测试代码：
#include
#include "min_max_heap.h"
#include
#include
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? ?cout<? cout<? min_max_heap hp(a,n);
? cout<<"The min-max heap: "<? cout<<"delmax(): ";
? for(int i=0; i? ?cout<? cout<? for(int i=0; i? ?hp.insert(a[i]);
? cout<<"The min-max heap: "<? cout<<"delmin(): ";
? for(int i=0; i? ?cout<? cout<? cin>>n;
?}
}
int* create_array(const int n)
{
?int* res = new int[n];
?for(int i=0; i? res[i] = 0;
?for(int i=0; i?{
? srand((unsigned)time(0));
? while(1)
? {
? ?int m=rand()%n;
? ?if(res[m] ==0)
? ?{
? ? res[m] = i;
? ? break;
? ?}
? }
?}
?return res;
}
上述代码只是我在学习min-max heap 时使用的测试代码，如有什么不明白的地方欢迎讨论。