一般情況下我們使用的堆都是大頂堆或者小頂堆，其能實現在常數時間內獲得數組的最大值或者最小值，同時滿足在對數時間內刪除和插入元素。但是如果要同時實現即能在常數時間內獲得最大值和最小值，又能在對數時間內刪除和插入元素，通常情況下的堆就不能滿足上述要求了。為此介紹一種新的數據結構min-max heap
min-max heap 是一顆完全二叉樹，但是二叉樹的奇數層存的是max元素，偶數層存的是min元素，也即在以偶數層的某節點為根節的子樹中，根節點最大，若在以奇數層為根節點的子樹中，根節點最小。根據上述的思想構造出相應的min-max heap。
二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm
【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm
在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm
【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm
二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm
二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm
輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm
算法實現：
#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 時使用的測試代碼，如有什麼不明白的地方歡迎討論。
