小顶混合堆的实现与应用(a min

一般情况下我们使用的堆都是大顶堆或者小顶堆，其能实现在常数时间内获得数组的最大值或者最小值，同时满足在对数时间内删除和插入元素。但是如果要同时实现即能在常数时间内获得最大值和最小值，又能在对数时间内删除和插入元素，通常情况下的堆就不能满足上述要求了。为此介绍一种新的数据结构min-max heap

min-max heap 是一颗完全二叉树，但是二叉树的奇数层存的是max元素，偶数层存的是min元素，也即在以偶数层的某节点为根节的子树中，根节点最大，若在以奇数层为根节点的子树中，根节点最小。根据上述的思想构造出相应的min-max heap。

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在Java中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

算法实现：

#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;
}