Algorithms: 数组堆 - JAVA

/*-----------------------------------------------------------------------------------------------
 * Project: Heap.cpp
 * Name: zwp
 * Date: 2014/3
 *-----------------------------------------------------------------------------------------------*/


#ifndef HEAP_H_
#define HEAP_H_



#define TRUE  1
#define FALSE 0

struct HeapStruct;
typedef struct HeapStruct* PriorityQueue;

typedef int ElementType;

/*
** 初始化优先队列
*/
PriorityQueue Initialize(int MaxElements);

/*
** 销毁队列
*/
void Destroy(PriorityQueue H);


/*
** 建堆
*/
void MakeEmpty(PriorityQueue H);

/*
** 插入元素
*/
void Insert(ElementType x, PriorityQueue H);

/*
** 删除最小元素
*/
ElementType DeleteMin(PriorityQueue H);

/*
** 寻找最小元素
*/
ElementType FindMin(PriorityQueue H);


/*
** 判断队列是否为空
*/
int IsEmpty(PriorityQueue H);

/*
** 判断队列是否满
*/
int IsFull(PriorityQueue H);


/*
** 遍历堆
*/
void Tranver(PriorityQueue H);



#endif

/*----------------------------------------------------------------------------------------
 * Project: Heap.cpp
 * Name: zwp
 * Date: 2014.3
 *--------------------------------------------------------------------------------------*/




#include 
  
   
#include 
   
     #include "Heap.h" /* ** Place in implementaton */ struct HeapStruct { int Capacity; int size; ElementType* Elements; }; #define MinData 0 #define MinPQSize 10 int MinElement; /* ** 初始化队列 */ PriorityQueue Initialize(int maxElements) { PriorityQueue H; if(maxElements < MinPQSize) printf("Priority queue size is too small...\n"); H = (HeapStruct*)malloc(sizeof(struct HeapStruct)); if(H == NULL) printf("Out of space....\n"); H->Elements = (ElementType*)malloc((maxElements + 1) * sizeof(ElementType)); if(H->Elements == NULL) printf("Out of space...\n"); H->Capacity = maxElements; H->size = 0; H->Elements[0] = MinData; return H; } /* ** 清空队列 */ void MakeEmpty(PriorityQueue H) { H->size = 0; } /* ** 销毁队列 */ void Destroy(PriorityQueue H) { free(H->




Elements); free(H); } /* ** 插入元素 */ void Insert(ElementType X, PriorityQueue H) { int i; if(IsFull(H)) { printf("Priority queue is full....\n"); return ; } /* * left = i/2 * right = i/2 + 1 */ for(i = ++H->size; H->Elements[i/2] > X; i /= 2) H->Elements[i] = H->Elements[i/2]; H->Elements[i] = X; } /* ** 删除最小元素 */ ElementType DeleteMin(PriorityQueue H) { int i, Child; ElementType DeleteMin, LastElement; if(IsEmpty(H)) { printf("Priority queue is empty....\n"); return H->Elements[0]; } /* ** MinElement = root ** LastELement = last */ MinElement = H->Elements[i]; LastElement = H->Elements[H->size-1]; for(i = 1; i * 2 <= H->size; i = Child) { Child = i * 2; if(Child != H->size && H->Elements[Child+1] < H->Elements[Child]) Child++; /* Percolate one level */ if(LastElement > H->Elements[Child]) H->Elements[i] = H->Elements[Child]; else break; } H->Elements[i] = LastElement; return MinElement; } /* ** 寻找最小元素 */ ElementType FindMin(PriorityQueue H) { return H->Elements[0]; } /* ** 判断是否为空 */ int IsEmpty(PriorityQueue H) { if(H->size == 0) return TRUE; else return FALSE; } /* ** 判断队列是否满 */ int IsFull(PriorityQueue H) { return (H->size == H->Capacity)   TRUE : FALSE; } /* ** 遍历堆 */ void Tranver(PriorityQueue H) { for(int index = 0; index < H->size; ++ index) printf(" %d", H->Elements[index]); }

/*-----------------------------------------------------------------------
 * Project: Main.cpp
 * Name: zwp
 * Date: 2014/3
 *---------------------------------------------------------------------------*/



#include "Heap.h"
#include 
  
   
#include 
   
     int main(int argc, char* argv[]) { PriorityQueue H = Initialize(100); for(int index = 1; index < 98; ++ index) Insert(index+1, H); Insert(999, H); Insert(998, H); printf("The Min = %d\n\n", FindMin(H)); Tranver(H); system("pause"); return 0; }

Algorithms: 数组堆(一)