Binary heap (priority right column)

2010-06-25  来源:本站原创  分类:Tech  人气:147 

/*===========*\
 | binheap.h |
\*===========*/

#ifndef _BINHEAP_H_
#define _BINHEAP_H_
#define ElementType int
#define MinPQSize   2
#define MinData  -10000

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

//function list
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

/*=============*\
 |  binheap.c  |
\*=============*/

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

// Initialize the priority queue
PriorityQueue Initialize(int MaxElements)
{
        PriorityQueue h;

        if (MaxElements < MinPQSize)
                printf("out of space!!\n");

        h = (PriorityQueue)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;
}

// Determine whether the queue is full
int IsFull(PriorityQueue h)
{
        return h->Size == h->Capacity-1;
}

// Determine whether the queue is empty
int IsEmpty(PriorityQueue h)
{
        return h->Size == 0;
}

// Insert node
void Insert(ElementType x,PriorityQueue h)
{
        int i ;
        if (IsFull(h))
        {
                printf("Priority queue is full\n");
                return;
        }

        for(i=++h->Size;h->Elements[i/2]>x;i/=2)
                h->Elements[i] = h->Elements[i/2];
        h->Elements[i]=x;
}
// From node under filter p
void percolateDown(int p,PriorityQueue h)
{
        int i = p;
        if (p>h->Size)
        {
                printf("Out of the size !! : p=%d,size=%d\n",p,h->Size);
                return;
        }
        ElementType element = h->Elements[p];
        while (i*2<=h->Size)
        {
                int minChild = (2*i != h->Size) && (h->Elements[2*i]>h->Elements[2*i+1]) ? 2*i+1 : 2*i;
                if(element>h->Elements[minChild])
                {
                        h->Elements[i] = h->Elements[minChild];
                        i=minChild;
                }
                else
                        break;
        }
        h->Elements[i] = element;
}
// On the filter from the node P
void percolateUp(int p,PriorityQueue h)
{
        int i;
        if (p>h->Size)
        {
                printf("Out of the size !!\n");
                return;
        }
        ElementType element = h->Elements[p];
        for(i=p;h->Elements[i/2]>element;i=i/2)
                h->Elements[i] = h->Elements[i/2];
        h->Elements[i]=element;
}
// Remove smallest element
ElementType DeleteMin(PriorityQueue h)
{
        int i,Child;
        ElementType MinElement,LastElement;

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

        MinElement = h->Elements[1];
        LastElement = h->Elements[h->Size--];

        for(i=1;i*2<=h->Size;i=Child)
        {
                /* find smaller 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;
}
// Lower keyword value
void DecreaseKey(int P,ElementType value,PriorityQueue h)
{
        h->Elements[P] -= value;
        percolateUp(P,h);
}
// Increase keyword value
void IncreaseKey(int P,ElementType value,PriorityQueue h)
{
        h->Elements[P] += value;
        percolateDown(P,h);
}

// Delete a node
void Delete(int P,PriorityQueue h)
{
        DecreaseKey(P,-10000,h);
        DeleteMin(h);
}
// Building the reactor
void BuildHeap(ElementType * et,int n,PriorityQueue h)
{
        int i;
        h->Size = n;
        if (n>h->Capacity)
        {
                printf("Out of the capacity!\n");
                return;
        }
        for(i=0;i<n;i++)
        {
                h->Elements[i+1] = et[i];
        }

        for(i=n/2;i>0;i--)
                percolateDown(i,h);
}

// Print a binary heap  ( Priority queue  )
void printBinHeap(PriorityQueue h)
{
        int i;
        for(i=1;i<=h->Size;i++)
                printf("%d  ",h->Elements[i]);
        putchar('\n');
}
//////////////////////////////////////////////////////////////////////////
int main()
{
        ElementType a[]={19,18,7,3,4,9,11,22,12};
        PriorityQueue h = Initialize(20);
        BuildHeap(a,sizeof(a)/sizeof(int),h);
        printBinHeap(h);
        DecreaseKey(8,20,h);
        printBinHeap(h);
        IncreaseKey(1,20,h);
        printBinHeap(h);
        Delete(1,h);
        printBinHeap(h);
        Insert(3,h);
        printBinHeap(h);
        system("pause");
        return 0;
}
相关文章
  • Binary heap (priority right column) 2010-06-25

    /*===========*\ | binheap.h | \*===========*/ #ifndef _BINHEAP_H_ #define _BINHEAP_H_ #define ElementType int #define MinPQSize 2 #define MinData -10000 typedef struct HeapStruct { int Capacity; int Size; ElementType * Elements; } * PriorityQueue; //

  • [Switch] [translator] A * pathfinding in the use of binary heap 2010-11-07

    http://blog.vckbase.com/panic/archive/2005/03/28/4144.html In the A * pathfinding using binary heap Of: Patrick Lester (2003 Apr 2000 11 update) Translator: Panic 2005 Mar 2000 28 Day Translator order: In this article, is "A * Pathfinding for Beginne

  • A * pathfinding, and AS3 to achieve binary heap 2010-12-23

    Game times and warlords since the Central Plains Deere wayfinding is the first step, the importance of self-evident. This the first acquisition of tactical pathfinding A * algorithm, as we drill some, the deficiency also look let me know. Can choose

  • Heapsort 和 priority queue 2014-07-30

    一.二叉堆含义及属性: 堆(heap)亦被称为:优先队列(priority queue),是计算机科学中一类特殊的数据结构的统称.堆通常是一个可以被看做一棵完全二叉树的数组对象.在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权.堆即为解决此类问题设计的一种数据结构.同垃圾收集存储的堆含义不同. 表示堆的数组A有两个属性: A.length : 代表A数组的元素个数; A.heapsiz

  • On the heap (heap) and stack (stacks) of the problem: 2010-12-25

    On the heap (heap) and stack (stacks) of the problem: heap (heap): assigned by the programmer and recovery, if its end of the process, not recycling by the recovery of the operating system to complete the work. stack (stack): It is to be allocated by

  • Java heap to achieve the minimum 2010-05-31

    1. Heap node package boke.heap1; /** * Heap nexus * * @since jdk1.5 And above * @author Wool shokichi * @version 1.0 * @date 2010.05.24 * */ public class Node { private int iData; // Nexus data is an integral type public Node(int key) { iData = key;

  • Mass data processing feature (e) - heap 2010-12-03

    Transfer: http://blog.redfox66.com/post/mass-data-topic-5-heap.aspx What is the heap] [ Concept: A heap is a special kind of binary tree, with the following two properties 1) The value of each node is greater than (or less than, as the minimum heap)

  • Art of Computer Programming ----- heap sort 2010-12-22

    Heap Sort: A heap-based sorting algorithm; Heap defines some basic concepts: If and only if the sequence satisfies the following properties (referred to as the heap property): (1) ki ≤ K2i and ki ≤ K2i +1 or (2) Ki ≥ K2i and ki ≥ K2i +1 (1 ≤ i ≤ n) /

  • Simple _ construction of the heap 2011-10-16

    Reactor is a useful data structure is a binary tree representation of the array. Minimum and maximum heap heap is a binary heap of two forms. Maximum heap: the root node of the key is key in all the heap nodes greatest. Minimum heap: heap root keys a

  • golang 标准库 container/ring 及 container/heap 2015-03-18

    由于目前golang 没有提供泛型机制,所以通用容器实现基本和 c 类似,golang 用 interface{} 做转接, c 用 void * 转接. ring 包实现循环双向链表: type Ring struct { next, prev *Ring Value interface{} } 内部导出一个用户可以操作的Value 字段. heap 包实现 binary heap : type Interface interface { sort.Interface Push(x inter

  • Algorithm review reprint 2010-06-03

    Phase I: the classical training algorithm used, each of the following algorithm to me marked from 10 to 20 times, while streamlining their own code, Too common, so do not think when I got to write 10-15 minutes, slapping, or even turn off the monitor

  • [Change] How should master data structure. Commonly used algorithm 2010-07-05

    How should master data structure, commonly used algorithm Can not fully remember so many algorithms. Commonly used algorithms, can be written to take over is not commonly used, picked up the book, and looked for 10 minutes, you can understand the alg

  • [Transfer] learning algorithm of the Road 2010-10-08

    Learning algorithm of the Road Phase I: the classical training algorithm used, each of the following algorithm to me marked with ten to twenty times, while streamlining their own code, Too often, so when you do not want to be trained to write ,10-15

  • Java performance monitoring on the 5 things you do not know, Part 2 2010-10-24

    Description: If you configure a fully functional JDK JConsole analyzer or news for your case, this article will introduce the five independent analysis of the utility may make you feel more surprising. You will learn a lightweight (and sometimes expe

  • As3 game data structure (class package profile) 2010-11-04

    Quote Description: 'As3 game data structure' is a contains a Flash game for many common programming and application development of data structure packages. The cause of the project I did because I want a unified library for my game. Collections Almos

  • Principles of Database 2010-11-05

    This article reproduced from csdn, belongs to original author. How to learn SQL feilniu (AT) gmail.com wrote on 20100826 This follows the CC agreement, welcome to reprint Constantly see in the new forum to ask some basic questions. So find time to po

  • [Switch] [translator] A * pathfinding of GameDev.net 2010-11-07

    http://blog.vckbase.com/panic/archive/2005/03/20/3778.html A * pathfinding of GameDev.net Of: Patrick Lester Translator: Panic 2005 Mar 2000 18 Day Translator order: long ago that the A * algorithm, but never seriously read the related article, did n

  • [Transfer] the way learning algorithm 2010-11-27

    Phase I: the classical training algorithm used, each of the following algorithm to me marked with ten to twenty times, while streamlining their own code, Too often, so when you do not want to be trained to write ,10-15 minutes on shore, or even turn

  • Finishing the game algorithm 2010-12-22

    Algorithm for sorting algorithm for a game: A * pathfinding of Of: Patrick Lester Translator: Panic 2005 Mar 2000 18 Day Translator order: long ago that the A * algorithm, but never seriously read the related article, did not read the code, but my mi

  • Collection and General Collection [transfer] 2011-04-17

    Gong Yongsheng ( [email protected] ), Abstract: This paper describes the Jakarta project commons-collection, its current version is 2.1. This paper sets the framework for the collation and j2sdk sample can greatly speed up the example of programmers