堆（heap）操作集

作者: 日常表白结衣 | 来源:发表于2017-08-02 14:42 被阅读0次

堆（heap）操作集
Heap&HeapSort（MIT算法导论）
堆Heap
heap (堆)
Heap 堆
堆：Heap
堆 (Heap)
堆（Heap）
堆（heap）
堆 - Heap

优先队列（Priority Queue）：特殊队列，取出元素的顺序是依照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。
堆的特性
【1】结构性：用数组表示的完全二叉树
【2】有序性：任一节点的关键字是其子树所有节点的最大值（或者最小值）
最大堆（MaxHeap）：最大值
最小堆（MinHeap）：最小值
【3】从根节点到任意节点路径上节点序列的有序性
【堆建立】
最大堆的建立：时间复杂性O(n) 树中各节点的高度和
将已经存在的N个元素按最大堆的要求存放在一个一维数组中
从倒数第一个有儿子的节点开始，将其调整成堆
然后从右向左，从下往上依次调整成堆
每当右父节点落下时，再调整成新的堆

/* 
  最大堆操作集
  堆是一种用数组表示的完全二叉树
  树:
  a
  bc
  defg
  hi######
  堆：#abcdefghi##,数组0为空
  若一个节点式i，则左儿子是2*i，右儿子是2*i+1
 */

#include<stdio.h>
#include<stdlib.h>

#define MaxData 1000
//#define MaxSize 10
typedef int ElementType;
struct HeapStruct{
    ElementType *Elements; //指向数组空间的指针（存储堆元素的一维数组）
    int Size; //当前数组长度
    int Capacity;//初始化时所定义的数组长度
};
typedef struct HeapStruct *MaxHeap;

MaxHeap CreateHeap(MaxHeap H,int MaxSize); //创建堆
void Insert(MaxHeap H,ElementType item); //插入元素item
ElementType DeleteMax(MaxHeap H); //取出二叉树根节点，同时删除一个节点
int IsFull(MaxHeap H, int MaxSize);//判断堆为空
int IsEmpty(MaxHeap H);//判断堆为满

int main()
{
  int MaxSize=10;
    int arrary[] = {58,25,44,18,10,26,20,12,8};
    MaxHeap heap=NULL;
    heap=CreateHeap(heap,MaxSize);
  for(int i=0;i<10;i++){
    Insert(heap,arrary[i]);
  }

  while(!IsEmpty(heap)){
    printf("%d, ", DeleteMax(heap));
  }
  putchar('\n');
  printf("%d\n",heap->Elements[0]);
    system("pause");
    return 0;
}

MaxHeap CreateHeap(MaxHeap H,int MaxSize)
{
    H=(MaxHeap)malloc(sizeof(struct HeapStruct));
    /*
    这一块卡了好久、关于内存那里搞错了
    int *p;
    p=(int *)malloc(sizeof(int));
    p=NULL;
  */
    H->Elements=(ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
    H->Size=0;
    H->Capacity=MaxSize;
  //最大值用作哨兵，以便于以后更快操作
    H->Elements[0]=MaxData;

  return H;
}

int IsFull(MaxHeap H,int MaxSize)
{
    if(H->Size== MaxSize) return 1;
  else  return 0;
}

int IsEmpty(MaxHeap H)
{
  if(H->Size==0)  return 1;
  else return 0;
}

/* 将新增节点插入到其从父节点到根节点的有序序列中 */
void Insert(MaxHeap H,ElementType item)
{
  /* 将元素item插入最大堆H，其中H->Elements[0] */
    int i;
    if(IsFull(H, 10)){
        printf("the head is full\n");
    }else{
    i = ++H->Size; //i指向插入后堆中的最后一个元素的位置,其父节点是H->Elements[i/2]
    //过滤插入
    for( ;H->Elements[i/2]<item;i/=2)//与父节点做比较，满足插入的有序性
      //哨兵为最大值，在[0]位置，在比较过程中，比哨兵小，则自然落在了根节点的位置
       H->Elements[i]=H->Elements[i/2];
    H->Elements[i]=item;
  }
}

/* 
   最大堆的删除：（根节点是最大值）
   取出根节点（最大值）元素，同时删除堆的一个节点 
   先用最后一个元素替换根节点，
   然后再比较较大的孩子，节点下沉，保证有序性
*/
ElementType DeleteMax(MaxHeap H)
{
    int parent,child;
    ElementType MaxItem,temp;
    if(IsEmpty(H)){
        printf("the MaxHeap is empty\n");
        return NULL;
    }
    MaxItem=H->Elements[1]; //保存要删除的元素，即堆的最大值
    temp=H->Elements[H->Size--]; //用最大堆中最后一个元素从节点开始向上过滤下层节点
    /* 
       parent*2<=H->Size 判别是否有左孩子 
       从左右儿子中找到一个大的值与节点比较
       将child变量指向左右儿子中较大的的一个
    */
    for(parent=1;parent*2<=H->Size;parent=child){
        child=parent*2; //child 指向左儿子；child+1 指向右儿子
        if((child!=H->Size)&&(H->Elements[child]<H->Elements[child+1]))
            child++;
        if(temp>=H->Elements[child]) break;
        else
            H->Elements[parent]=H->Elements[child]; //较大值上浮
    }
    H->Elements[parent]=temp;
    return MaxItem;
}

最小堆操作集

/* 最小堆操作集 */

#include<stdio.h>
#include <stdlib.h>

#define MinData -1
#define MaxSize 101
typedef int ElemnetType;
typedef struct HeapStruct{
    ElemnetType *Elements;
    int Size;
    int Capacity;
}*MinHeap;

MinHeap CreateHeap(MinHeap H);
void Inster(MinHeap H,ElemnetType item);
int IsFull(MinHeap H);
int IsEmpty(MinHeap H);
ElemnetType DeleteMin(MinHeap H);

int main()
{
    int arr[]={23,26,46,24,10};
    MinHeap heap=NULL;

    heap=CreateHeap(heap);
    for(int i=0;i<5;i++){
        Inster(heap,arr[i]);
    }

    while(!IsEmpty(heap)){
        printf("%d, ", DeleteMin(heap));
    }
    putchar('\n');

    system("pause");
    return 0;
}

MinHeap CreateHeap(MinHeap H)
{
    H=(MinHeap)malloc(sizeof(struct HeapStruct));
    H->Elements=(ElemnetType *)malloc(sizeof(ElemnetType));
    H->Size=0;
    H->Capacity=MaxSize;
    H->Elements[0]= MinData;

    return H;
}

int IsFull(MinHeap H)
{
    if(H->Size==MaxSize)    return 1;
    else return 0;      
}

int IsEmpty(MinHeap H)
{
    if(H->Size==0)  return 1;
    else return 0;
}

void Inster(MinHeap H,ElemnetType item)
{
    int i;
    if(IsFull(H)){
        printf("Full\n");
    }else{
        i=++H->Size;
        for( ;item<H->Elements[i/2];i/=2)
            H->Elements[i]=H->Elements[i/2];
        H->Elements[i]=item;
    }
}

ElemnetType DeleteMin(MinHeap H)
{
    int parent,child;
    ElemnetType MinItem,temp;
    if(IsEmpty(H)){
        printf("Empty\n");
        return NULL;
    }
    MinItem=H->Elements[1];
    temp=H->Elements[H->Size--];
    for(parent=1;parent*2<H->Size;parent=child){
        child=parent*2;
        if((child!=H->Size)&&(H->Elements[child]>H->Elements[child+1]))
            child++;
        if(temp<H->Elements[child]) break;
        else
            H->Elements[parent]=H->Elements[child];
    }
    H->Elements[parent]=temp;

    return MinItem;
}