优先队列--堆

虽然求最小值的操作可以在常数时间完成，但是，按照最小元设计的堆（也称作最小堆）在求最大元方面却无任何帮助，事实上，一个堆所蕴含的关于序的信息很有限，因此，若不对整个堆进行线性搜索，是没有办法找出任何特定的关键字的。（《数据结构与算法分析——C语言描述》之6.3.4节）

从下面第二个图也可以看出，数据仅仅只是局部有序，整体来看并无顺序可言。可以使用该方法来找出最小或者最大的数。

#ifndef _BINHEAP_H_
#define _BINHEAP_H_

typedef int ElementType;
struct HeapStruct
{
    int Capacity;
    int Size;
    ElementType *Elements;
};

typedef struct HeapStruct *PriorityQueue;

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);

#endif

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

#define MinPQSize 5
#define Mindata 0

int IsFull(PriorityQueue H)
{
    return H->Size == H->Capacity;
}

int IsEmpty(PriorityQueue H)
{
    return H->Size==0?1:0;
}

PriorityQueue Initialize(int MaxElements)
{
    PriorityQueue H;

    if(MaxElements < MinPQSize)
    {
        printf("priority queue size is too small\n");
        return NULL;
    }

    H=(PriorityQueue)malloc(sizeof(struct HeapStruct));
    if(H==NULL)
    {
        printf("malloc error\n");
        return NULL;
    }

    H->Elements=malloc((MaxElements+1)*sizeof(ElementType));
    if(H->Elements==NULL)
    {
        printf("H->elements malloc error\n");
        free(H);
        return NULL;
    }

    H->Capacity=MaxElements;
    H->Size=0;
    H->Elements[0]=Mindata;

    return H;
}

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

    /*
    对于数组任意位置i上的元素，起左儿子在位置2i,右儿子在2i+1,他的父亲则在位置[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 MinElement,LastElement;

    if(IsEmpty(H))
    {
        printf("Priority queue is empty\n");
        return H->Elements[0];
    }

    MinElement=H->Elements[1];
    LastElement=H->Elements[H->Size--];
    for (i=1;i*2<=H->Size;i=Child)
    {
        Child=i*2;
        if(Child!=H->Size && H->Elements[Child+1]<H->Elements[Child])
        {
            Child++;
        }
        if(LastElement>H->Elements[Child])
        {
            H->Elements[i]=H->Elements[Child];
        }
        else
        {
            break;
        }
    }
    H->Elements[i]=LastElement;
    return MinElement;   
}

#include <stdio.h>
#include "heap.h"

int main(void)
{
    PriorityQueue q=Initialize(16);
    int array[]={1,3,56,22,8,9,5,4,6,34,17};
    int i;

    if(q==NULL)
    {
        printf("q malloc error\n");
        return 0;
    }

    for(i=0;i<sizeof(array)/sizeof(int);i++)
    {
        Insert(array[i],q);
        printf("array[%d]=%2d\n",i,array[i]);
    }

    for(i=1;i<sizeof(array)/sizeof(int)+1;i++)
    {
        printf("q->Elements[%d]=%2d\n",i,q->Elements[i]);
    }

    for(i=0;i<sizeof(array)/sizeof(int);i++)
    {
        printf("%d:%d\n",i+1,DeleteMin(q));
    }

    return 0;
}

1 2	$ gcc -o main main.c heap.c ^C $ ./main

其它应用方面。比如可能有一些作业特别重要，需要打印机一有空闲就来处理该作业。这就相当于在一系列的任务中，优先执行一个高优先级的任务。这里说一个实际案例。

在自动抄表中，集中器会自动地定时的进行抄表，并将数据上传至服务器。如果此时服务器端有手动的抄表动作，那么集中器需要暂停当前的自动抄表动作，而去执行服务器的抄表动作。一是因为一个集中器设备下面会有很多的表，完成所有的抄表动作需要一定的时间；二是提高服务器端的响应时间，属于一种人性化设计，否则服务器端可能需要等待几分钟才能看到所要的结果，给人的感觉就不好。

当然服务器端也可以实现自动抄表，集中器采集器仅仅作为数据转发设备，该方案此处不提。当时的设计是在集中器实现自动抄表。优先响应服务器的抄表指令使用的是高优先级任务的方式，即每完成一次抄表，检查是否有服务器抄表命令，如果有那么就进行一次任务调度，执行服务器抄表指令，否则继续执行自动抄表。为何需要在每次抄表完成后才去检查？这涉及到抄表的执行流程，简单说来就是：集中器发送抄表指令，表计会通过总线接收指令，之后进行应答，集中器接收数据。这个过程需要一定的时间，并且因为所有表计均挂在总线上，所以一定要等待上一次抄表完成之后才能进行下一次抄表，否则数据就会冲突。

堆排序（2021-6-11 16:48:45）

直接将数组中的数据变为堆的形式，数据取出之后还是放入数组中，结果就是升序或者降序排列。


/****************************************************/
/*堆排序*/
void Swap(int *a,int *b)
{
    int tmp=*a;

    *a=*b;
    *b=tmp;
}

#define LeftChiild(i) (2*(i)+1)
void PercDown(ElementType A[],int i,int N)
{
    int Child;
    ElementType Tmp;

    for (Tmp=A[i];LeftChiild(i)<N;i=Child)
    {
        Child=LeftChiild(i);
        if(Child!=N-1 && A[Child+1]>A[Child])
        {
            Child++;
        }
        if(Tmp<A[Child])
        {
            A[i]=A[Child];
        }
        else
        {
            break;
        }
    }
    A[i]=Tmp;
}

void HeapSort(ElementType A[],int N)
{
    int i;

    for(i=N/2;i>=0;i--)//buile heap
    {
        PercDown(A,i,N);
    }

    for(i=N-1;i>0;i--)//delete max
    {
        Swap(&A[0],&A[i]);
        PercDown(A,0,i);
    }
}

void PercUp(ElementType A[],int i,int N)
{
    int Child;
    ElementType Tmp;

    for (Tmp=A[i];LeftChiild(i)<N;i=Child)
    {
        Child=LeftChiild(i);
        if(Child!=N-1 && A[Child+1]<A[Child])
        {
            Child++;
        }
        if(Tmp>A[Child])
        {
            A[i]=A[Child];
        }
        else
        {
            break;
        }
    }
    A[i]=Tmp;
}

void HeapSort_UP(ElementType A[],int N)
{
    int i;

    for(i=N/2;i>=0;i--)//buile heap
    {
        PercUp(A,i,N);
    }

    for(i=N-1;i>0;i--)//delete max
    {
        Swap(&A[0],&A[i]);
        PercUp(A,0,i);
    }
}

int main(void)
{
    PriorityQueue q=Initialize(16);
    int array[]={1,3,56,22,8,9,5,4,6,34,17};
    int i;

    /****************************************************/
    printf("HeapSort:\n");
#if 1// 升序
    HeapSort(array,sizeof(array)/sizeof(int));//最大堆
    for(i=0;i<sizeof(array)/sizeof(int);i++)
    {
        printf("array[%d]=%2d\n",i,array[i]);
    }
#else　//降序
    /****************************************************/
    HeapSort_UP(array,sizeof(array)/sizeof(int));//最小堆
    for(i=0;i<sizeof(array)/sizeof(int);i++)
    {
        printf("array[%d]=%2d\n",i,array[i]);
    }
#endif
    /****************************************************/
    return 0;
}

运行结果如下