当前访客身份:游客 [ 登录 | 加入 OSCHINA ]

代码分享

当前位置:
代码分享 » C/C++  » 编程基础
不是胖子

优先队列

不是胖子 发布于 2013年03月26日 11时, 0评/669阅
分享到: 
收藏 +0
2
使用二叉堆实现优先队列
标签: <无>

代码片段(1) [全屏查看所有代码]

1. [文件] binheap.c ~ 3KB     下载(22)     跳至 [1] [全屏预览]

// 二叉堆实现优先队列
// Bery 2013-03-26
#include <stdio.h>

#define MINDATA -32767

// 二叉堆
typedef struct HeapStruct 
{
    int capacity;       // 最大堆容量
    int size;           // 当前堆大小
    int * element;      // 节点指针
} * PriorityQueue;

// 初始化
PriorityQueue Initialize(int capacity)
{
    PriorityQueue h = (PriorityQueue)malloc(sizeof (struct HeapStruct));    
    
    h->element = (int *)malloc((capacity + 1) * sizeof (int));
    h->capacity = capacity;
    h->size = 0;

    // 将堆的顶端存入最小值, 作为标志位
    h->element[0] = MINDATA;

    return h;
}

// 入队
void Insert(int e, PriorityQueue h)
{
    int i;      // 索引
    if (h->size == h->capacity)
    {
        printf("队满, 入队失败. \n");
        return;
    }

    h->size++;  
    
    // 从队尾元素开始, 找到元素要入队的位置
    for (i = h->size; h->element[i / 2] > e; i = i / 2)
        h->element[i] = h->element[i / 2];
    h->element[i] = e;
}

// 出队
int DeleteMin(PriorityQueue h)
{
    int i;          // 索引
    int child;      // 子元素
    int min;        // 最小值
    int last;       // 队尾元素
    
    if (h->size == 0)
    {
        printf("队空, 出队失败 \n");
        return 0;
    }

    min = h->element[1];            // 要出队的元素
    last = h->element[h->size];     // 队尾元素未必是最大值
    h->size--;

    for (i = 1; i * 2 <= h->size; i = child)
    {
        // 计算i的左子树
        child = i * 2;  

        // 如果i的右子树小于左子树, 则使child指向右子树
        if (child != h->size && h->element[child + 1] < h->element[child])
            child++;

        // 如果队尾元素大于当前节点的最小子树, 则把子树赋给当前节点
        // 否则退出循环
        if (last > h->element[child])
            h->element[i] = h->element[child];
        else
            break;
    }

    // 当前节点的位置应存入last
    h->element[i] = last;

    return min;
}

int main(void)
{
    int i;
    int size;

    PriorityQueue h = Initialize(20);
    
    Insert(13, h);
    Insert(14, h);
    Insert(16, h);
    Insert(19, h);
    Insert(21, h);
    Insert(29, h);
    Insert(68, h);
    Insert(65, h);
    Insert(26, h);
    Insert(32, h);
    Insert(31, h);

    size = h->size;

    // 遍历所有元素
    for (i = 0; i < size; i++)
        printf("%d\t", DeleteMin(h));

    return 0;
}


开源中国-程序员在线工具:Git代码托管 API文档大全(120+) JS在线编辑演示 二维码 更多»

开源从代码分享开始 分享代码
不是胖子的其它代码 全部(11)...