数据结构堆的向量实现

 

 

数据结构堆的向量实现
/**//*********************************************************************
Title:C++数据结构堆
Author:Zhen.liang 
CopyRight:Diyinside Community CSTC
包括最小堆和最大堆两部分组成
*********************************************************************/
/**//*
for example:
#include <iostream>
#include "Heap.h"
using namespace std;
int main(){
 DiyinsideHeap::MaxHeap<char> cdata(30);
 cdata.Insert('3');
 cdata.Insert('e');
 cdata.Insert('k');
 cout<<"Demo MinHeap"<<endl;
 while(!cdata.IsEmpty()){
  cout<<cdata.RemoveMin()<<endl;
 }
 return 0;
}
*/
 
#include <vector>
#include <assert.h>
using namespace std;
namespace DiyinsideHeap...{
 //最小堆
 template<class Type>
 class MinHeap...{
 public:
  //构造函数空堆
  MinHeap(int maxsize = 10)...{
   assert(maxsize>=0);//限制输入大小为正
   MaxHeapSize = maxsize;//堆大小
   CurrentSize = 0;//当前存放大小
   data.resize(MaxHeapSize);//存储空间设置
  }
  //析构函数
  ~MinHeap()...{
   data.clear();
  }
  int HeapSize()const;//获得Heap大小
  int Insert(const Type&);//插入元素
  Type RemoveMin();//删除最小的元素
  int IsEmpty()const;//判断是否空
  int IsFull()const;//判断是否满
  int MakeEmpty();//置空
 private:
  vector<Type> data;//存储数组
  int CurrentSize;//当前存放个数
  int MaxHeapSize;//最大存放个数
  int FilterDown(int,int);//向下调整
  int FilterUp(int);//向上调整
 };
 template<class Type>
 int MinHeap<Type>::HeapSize()const...{
  return CurrentSize;
 }
 template<class Type>
 int MinHeap<Type>::MakeEmpty()...{
  CurrentSize = 0;
  return 1;
 }
 template<class Type>
 Type MinHeap<Type>::RemoveMin()...{
  if(!CurrentSize)...{
   return -1;
  }
  else...{
   Type temp = data[0];
   data[0] = data[CurrentSize-1];
   CurrentSize--;
   FilterDown(0,CurrentSize-1);
   return temp;
  }
 }
 template<class Type>
 int MinHeap<Type>::IsFull()const...{
  if(CurrentSize == MaxHeapSize)...{
   return 1;
  }
  else...{
   return 0;
  }
 }
 template<class Type>
 int MinHeap<Type>::Insert(const Type& Data)...{
  if(CurrentSize == MaxHeapSize)...{
   return -1;
  }
  else...{
   data[CurrentSize] = Data;
   FilterUp(CurrentSize++);
   return 1;
  }
 }
 template<class Type>
 int MinHeap<Type>::FilterUp(int start)...{
  int j = start ;
  int i = (j-1)/2;
  Type temp = data[j];
  while(j>0)...{
   if(data[i]<=temp)...{
    break;
   }
   else...{
    data[j] = data[i];
    j = i;
    i = (i - 1)/2;
   }
  }
  data[j] = temp;
  return 1;
 }
 template<class Type>
 int MinHeap<Type>::FilterDown(int start,int end)...{
  int i = start ;
  int j = 2*i + 1;
  Type temp = data[i];
  while(j<=end)...{
   if((j<end) && (data[j]>data[j+1]))...{
    j++;
   }
   if(temp<=data[j])...{
    break;
   }
   else...{
    data[i] = data[j];
    i = j;
    j = 2*j + 1;
   }
  }
  data[i] = temp;
  return 1;
 }
 template<class Type>
 int MinHeap<Type>::IsEmpty()const...{
  if(CurrentSize)...{
   return 0;
  }
  else...{
   return -1;
  }
 }

 //最大堆
 template<class Type>
 class MaxHeap...{
 public:
  //构造函数空堆
  MaxHeap(int maxsize = 10)...{
   assert(maxsize>=0);
   MaxHeapSize = maxsize;
   CurrentSize = 0;
   data.resize(MaxHeapSize);
  }
  //析构函数
  ~MaxHeap()...{
   data.clear();
  }
  int HeapSize()const;//获得Heap大小
  int Insert(const Type&);//插入元素
  Type RemoveMin();//删除最小的元素
  int IsEmpty()const;//判断是否空
  int IsFull()const;//判断是否满
  int MakeEmpty();//置空
 private:
  vector<Type> data;//存储数组
  int CurrentSize;//当前存放个数
  int MaxHeapSize;//最大存放个数
  int FilterDown(int,int);//向下调整
  int FilterUp(int);//向上调整
 };
 template<class Type>
 int MaxHeap<Type>::HeapSize()const...{
  return CurrentSize;
 }
 template<class Type>
 int MaxHeap<Type>::MakeEmpty()...{
  CurrentSize = 0;
  return 1;
 }
 template<class Type>
 Type MaxHeap<Type>::RemoveMin()...{
  if(!CurrentSize)...{
   return -1;
  }
  else...{
   Type temp = data[0];
   data[0] = data[CurrentSize-1];
   CurrentSize--;
   FilterDown(0,CurrentSize-1);
   return temp;
  }
 }
 template<class Type>
 int MaxHeap<Type>::IsFull()const...{
  if(CurrentSize == MaxHeapSize)...{
   return 1;
  }
  else...{
   return 0;
  }
 }
 template<class Type>
 int MaxHeap<Type>::Insert(const Type& Data)...{
  if(CurrentSize == MaxHeapSize)...{
   return -1;
  }
  else...{
   data[CurrentSize] = Data;
   FilterUp(CurrentSize++);
   return 1;
  }
 }
 template<class Type>
 int MaxHeap<Type>::FilterUp(int start)...{
  int j = start ;
  int i = (j-2)/2;
  Type temp = data[j];
  while(j>0)...{
   if(data[i]>=temp)...{
    break;
   }
   else...{
    data[j] = data[i];
    j = i;
    i = (i - 2)/2;
   }
  }
  data[j] = temp;
  return 1;
 }
 template<class Type>
 int MaxHeap<Type>::FilterDown(int start,int end)...{
  int i = start ;
  int j = 2*i + 1;
  Type temp = data[i];
  while(j<=end)...{
   if((j<end) && (data[j]<data[j+1]))...{
    j++;
   }
   if(temp>=data[j])...{
    break;
   }
   else...{
    data[i] = data[j];
    i = j;
    j = 2*j + 1;
   }
  }
  data[i] = temp;
  return 1;
 }
 template<class Type>
 int MaxHeap<Type>::IsEmpty()const...{
  if(CurrentSize)...{
   return 0;
  }
  else...{
   return -1;
  }
 }
}
pku1442

#include <stdio.h>
#include <memory.h>
#include <queue>
using namespace std;


const int MAXN=30005;


struct TMax
{
TMax(int tx):x(tx) {}
int x;
};


struct TMin
{
TMin(int tx):x(tx) {}
int x;
};


int d[MAXN],g[MAXN];
int n,m;
priority_queue<TMax> hmax;
priority_queue<TMin> hmin;


bool operator<(const TMax &a,const TMax &b)
{
return a.x<b.x;
}


bool operator<(const TMin &a,const TMin &b)
{
return a.x>b.x;
}


void Read()
{
memset(d,0,sizeof(d));
memset(g,0,sizeof(g));
scanf("%d%d",&n,&m);
int i;
for (i=1;i<=n;i++) scanf("%d",&d[i]);
for (i=1;i<=m;i++) scanf("%d",&g[i]);
}


void Work()
{
int i,j=1;
for (i=1;i<=n;i++)
{
   if (!hmax.empty()&&d[i]<hmax.top().x)
   {
    hmin.push(TMin(hmax.top().x));
    hmax.pop();
    hmax.push(TMax(d[i]));
   }
   else hmin.push(TMin(d[i]));
   while (j<=m&&g[j]==i)
   {
    printf("%d\n",hmin.top().x);
    hmax.push(TMax(hmin.top().x));
    hmin.pop();
    j++;
   }
}
}


int main()
{
//freopen("in.txt","r",stdin);
Read();
Work();
return 1;
}

用堆实现优先队列

#include<stdio.h>
    
  typedef struct  
  {      
  int   Object_ID;       
  int   Priority;   
  }HEAP;   
    
  void   siftdown(HEAP*   a,int   i,int   n)   
  {   //adjust the factors' order
  int   j;   
  HEAP   t;   
  t=a[i];   
  while((j=2*i+1)<n)   
          {   
              if(j<n-1&&a[j].Priority<a[j+1].Priority)   j++;   
              if(t.Priority<a[j].Priority)   
			  {   
                 a[i]=a[j];   
                 i=j;   
			  }   
               else   break;   
  }   
           a[i]=t;   
  }   
    
  void   heap_sort(HEAP*   a,int   n)   
  {//put the factors in hesp for each time and sort them for each time
   int   i;   
   HEAP   t;   
   for(i=(n-2)/2;i>=0;i--)   
      siftdown(a,i,n);   
   for(i=n-1;i>0;i--)   
   {   
    t=a[0];   
    a[0]=a[i];   
    a[i]=t;   
    siftdown(a,0,i);   
   }
  }   
    
  void   changeweight(HEAP*   a,int&   num,int   Object_ID,   int   new_priority)   
  {   
    for(int i=0;i<num;i++)   
    if(a[i].Object_ID==Object_ID)   break;   
    if(i==num)   printf("No   such   Object_ID!\n");   
    a[i].Priority=new_priority;   
    heap_sort(a,num);   
  }   
    
  void   dequeue(HEAP*   a,int&   num,int&   Object_ID)   
  {   
          Object_ID=a[0].Object_ID;   
          for(int   i=0;i<num-1;i++)   
              a[i]=a[i+1];   
          num--;   
          heap_sort(a,num);   
  }   
    
    
  void   enqueue(HEAP*   a,int   &num,int   Object_ID,   int   priority)   
  {   
        a[num].Object_ID=Object_ID;   
        a[num++].Priority=priority;   
  }   
    
    
  bool   isLeaf(HEAP   *h,int&   num,int   i)     
  {   
  if(i>num/2)   return   true;   
  return   false;   
  }   
    
  int   leftChild(HEAP   *h,int&   num,int   i)   
  {   
  if(2*i>num)   return   -1;     //the   node   has   not   a   left   child   
  return   2*i;   
  }   
    
  void   main()   
  {   
        int   Object_ID,Priority;   
        HEAP   h[50];   
        int   num;   
    
        num=0;   
        while(Object_ID)   
        {   
		scanf("%d%d",&Object_ID,&Priority);
                if(!Object_ID)   break;   
        enqueue(h,num,Object_ID,Priority);   
        }   
        heap_sort(h,num);   
        for(int   i=0;i<num;i++)   
		   printf("%d\t%d\n",h[i].Object_ID,h[i].Priority);
  }