大-小顶混合堆的实现与应用（a min-max heap）

一般情况下我们使用的堆都是大顶堆或者小顶堆，其能实现在常数时间内获得数组的最大值或者最小值，同时满足在对数时间内删除和插入元素。但是如果要同时实现即能在常数时间内获得最大值和最小值，又能在对数时间内删除和插入元素，通常情况下的堆就不能满足上述要求了。为此介绍一种新的数据结构min-max heapmin-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 时使用的测试代码，如有什么不明白的地方欢迎讨论。本文永久更新链接地址：http://www.linuxidc.com/Linux/2014-11/109819.htm