C language implementation code of priority queue of priority_queue

  • 2020-04-02 01:46:18
  • OfStack

Priority queue (priority_queue) has the same functional interface as a normal queue, except that the smallest (or largest) element of the entire queue is sent out each time.

This paper briefly introduces a priority queue implemented based on array binary heap. The data structure defined and the function interface implemented are described as follows:

KeyValue pair structure: KeyValue


// =============KeyValue Struct==================================
typedef struct key_value_struct KeyValue;
struct key_value_struct
{
 int _key;
 void *_value;
};
KeyValue *key_value_new(int key, void *value);
void key_value_free(KeyValue *kv, void (*freevalue)(void *));

The key-value pair is the save form of the data in the priority queue, where the key is used to hold the priority and the _value is used to point to the actual data.

Key_value_new is used to create a KeyValue structure. Key_value_free is used to free the memory of a KeyValue structure,

The parameter freevalue is used to free the memory that the data pointer _value points to.

2. PriorityQueue structure: PriorityQueue


// =============PriorityQueue Struct==============================
#define PRIORITY_MAX 1
#define PRIORITY_MIN 2
typedef struct priority_queue_struct PriorityQueue;
struct priority_queue_struct
{
 KeyValue **_nodes;
 int _size;
 int _capacity;
 int _priority;
};
PriorityQueue *priority_queue_new(int priority);
void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *));
const KeyValue *priority_queue_top(PriorityQueue *pq);
KeyValue *priority_queue_dequeue(PriorityQueue *pq);
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);
int priority_queue_size(PriorityQueue *pq);
int priority_queue_empty(PriorityQueue *pq);
void priority_queue_print(PriorityQueue *pq);

1)   Where the nodes field is a binary heap array, _capacity is the number of KeyValue* Pointers to nodes, and _size is the number of elements actually stored in nodes.

        _priority can be PRIORITY_MAX or PRIORITY_MIN, indicating the maximum and minimum element priority, respectively.

2)   Priority_queue_new and priority_queue_free are used to create and release priority queues, respectively.

3)   Priority_queue_top is used to get the queue head element,

4) priority_queue_dequeue is used to get the head element of the queue and to unqueue the element.

The basic idea of its implementation with the maximum priority queue is as follows:

Save the first node [0] of the queue as the return value

Put nodes[_size-1] at nodes[0] and make _size=_size-1

(3) make parent(nodes[I]) equal to the new queue header (I =0) element,

Left = nodes[2 * I + 1] and rigth = nodes[2 * I + 2],

Compare left and right to get the son node with high priority, set as nodes[j](j = 2 * I + 1 or 2 * I + 2),

If the priority of the current parent node parent is higher than nodes[j], exchange nodes[I] and nodes[j], and update the current parent node,

I =j, and loop;

If the current parent node has a lower priority than nodes[j], processing ends.

5) priority_queue_enqueue is used to column the KeyValue

The basic idea of its implementation with the maximum priority queue is as follows:

Set nodes[_size] as the new KeyValue, and make _size++

Make the current child node (nodes[I]) the new queue tail node (I =_size-1), and the parent node of the child is nodes[j],

          The j =   I minus 1 over 2

If the priority of the current child node is higher than parent, exchange nodes[I] and nodes[j], and update the current child node

          I = j, and loop;

  If the current child node has a lower priority than parent, processing ends.

6)   Priority_queue_size is used to get the number of elements in the queue, and priority_queue_empty is used to determine whether the queue is empty.

7) priority_queue_print is used to output the contents of the queue.

File pq.h gives the declaration of data structure and function, file pq.c gives the concrete implementation, and main. C file is used for testing. Although it is the C language of procedural programming, we can see that the object-based idea is applied in specific coding, and we have done a certain degree of aggregation and encapsulation of data structures and related functions.



#ifndef _PRIORITY_QUEUE_H
#define _PRIORITY_QUEUE_H
// =============KeyValue Struct==================================
typedef struct key_value_struct KeyValue;
struct key_value_struct
{
      int _key;
      void *_value;
};
KeyValue *key_value_new(int key, void *value);
void key_value_free(KeyValue *kv, void (*freevalue)(void *));
// =============PriorityQueue Struct==============================
#define PRIORITY_MAX 1
#define PRIORITY_MIN 2
typedef struct priority_queue_struct PriorityQueue;
struct priority_queue_struct
{
      KeyValue **_nodes;
      int _size;
      int _capacity;

      int _priority;
};
PriorityQueue *priority_queue_new(int priority);
void priority_queue_free(PriorityQueue *pq, void (*freevalue)(void *));
const KeyValue *priority_queue_top(PriorityQueue *pq);
KeyValue *priority_queue_dequeue(PriorityQueue *pq);
void priority_queue_enqueue(PriorityQueue *pq, KeyValue *kv);
int priority_queue_size(PriorityQueue *pq);
int priority_queue_empty(PriorityQueue *pq);
void priority_queue_print(PriorityQueue *pq);
#endif
/*
*File:pq.c
*purpose: definition of priority queue in C
*Author:puresky
*Date:2011/04/27
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pq.h"
//Private Functions
static void priority_queue_realloc(PriorityQueue *pq);
static void priority_queue_adjust_head(PriorityQueue *pq);
static void priority_queue_adjust_tail(PriorityQueue *pq);
static int priority_queue_compare(PriorityQueue *pq,
    int pos1,
    int pos2);
static void priority_queue_swap(KeyValue **nodes,
  int pos1,
  int pos2);
//Functions of KeyValue Struct
KeyValue *key_value_new(int key,
             void *value)
{
      KeyValue *pkv = (KeyValue *)malloc(sizeof(KeyValue));
      pkv->_key = key;
      pkv->_value = value;
      return pkv;
}
void key_value_free(KeyValue *kv,
       void (*freevalue)(void *))
{
      if(kv)
      {
            if(freevalue)
            {
                  freevalue(kv->_value);
            }
            free(kv);
      }
}

//Functions of PriorityQueue Struct
PriorityQueue *priority_queue_new(int priority)
{
      PriorityQueue *pq = (PriorityQueue *)malloc(sizeof(PriorityQueue));
      pq->_capacity = 11; //default initial value
      pq->_size = 0;
      pq->_priority = priority;

      pq->_nodes = (KeyValue **)malloc(sizeof(KeyValue *) * pq->_capacity);
      return pq;
}
void priority_queue_free(PriorityQueue *pq,
              void (*freevalue)(void *))
{
      int i;
      if(pq)
      {
            for(i = 0; i < pq->_size; ++i)
                  key_value_free(pq->_nodes[i], freevalue);
            free(pq->_nodes);
            free(pq);
      }
}
const KeyValue *priority_queue_top(PriorityQueue *pq)
{
      if(pq->_size > 0)
            return pq->_nodes[0];
      return NULL;
}
KeyValue *priority_queue_dequeue(PriorityQueue *pq)
{
      KeyValue *pkv = NULL;
      if(pq->_size > 0)
      {
            pkv = pq->_nodes[0];
            priority_queue_adjust_head(pq);
      }
      return pkv;
}
void priority_queue_enqueue(PriorityQueue *pq,
                   KeyValue *kv)
{
      printf("add key:%dn", kv->_key);
      pq->_nodes[pq->_size] = kv;
      priority_queue_adjust_tail(pq);
      if(pq->_size >= pq->_capacity)
            priority_queue_realloc(pq);
}
int priority_queue_size(PriorityQueue *pq)
{
      return pq->_size;
}
int priority_queue_empty(PriorityQueue *pq)
{
      return pq->_size <= 0;
}
void priority_queue_print(PriorityQueue *pq)
{
      int i;
      KeyValue *kv;
      printf("data in the pq->_nodesn");
      for(i = 0; i < pq->_size; ++i)
            printf("%d ", pq->_nodes[i]->_key);
      printf("n");

      printf("dequeue all datan");
      while(!priority_queue_empty(pq))
      {
            kv = priority_queue_dequeue(pq);
            printf("%d ", kv->_key);
      }
      printf("n");
}
static void priority_queue_realloc(PriorityQueue *pq)
{
      pq->_capacity = pq->_capacity * 2;
      pq->_nodes = realloc(pq->_nodes, sizeof(KeyValue *) * pq->_capacity);
}
static void priority_queue_adjust_head(PriorityQueue *pq)
{
      int i, j, parent, left, right;

      i = 0, j = 0;
      parent = left = right = 0;
      priority_queue_swap(pq->_nodes, 0, pq->_size - 1);
      pq->_size--;
      while(i < (pq->_size - 1) / 2)
      {
            parent = i;

            left = i * 2 + 1;
            right = left + 1;
            j = left;
            if(priority_queue_compare(pq, left, right) > 0)
                  j++;
            if(priority_queue_compare(pq, parent, j) > 0)
            {
                  priority_queue_swap(pq->_nodes, i, j);
                  i = j;
            }
            else
                  break;

      }

}
static void priority_queue_adjust_tail(PriorityQueue *pq)
{
      int i, parent, child;

      i = pq->_size - 1;
      pq->_size++;
      while(i > 0)
      {
            child = i;
            parent = (child - 1) / 2;

            if(priority_queue_compare(pq, parent, child) > 0)
            {
                  priority_queue_swap(pq->_nodes, child, parent);
                  i = parent;
            }
            else
                  break;

      }
}

static int priority_queue_compare(PriorityQueue *pq,
    int pos1,
    int pos2)
{
      int adjust = -1;
      int r = pq->_nodes[pos1]->_key - pq->_nodes[pos2]->_key;
      if(pq->_priority == PRIORITY_MAX)
            r *= adjust;
      return r;
}
static void priority_queue_swap(KeyValue **nodes,
  int pos1,
  int pos2)
{
      KeyValue *temp = nodes[pos1];
      nodes[pos1] = nodes[pos2];
      nodes[pos2] = temp;
}
/*
*File: main.c
*purpose: tesing priority queue in C
*Author:puresky
*Date:2011/04/27
*/
#include <stdio.h>
#include <stdlib.h>
#include "pq.h"
int main(int argc, char **argv)
{
      int i;
      PriorityQueue *pq = priority_queue_new(PRIORITY_MAX);

      
      int a[]={1, 9, 7, 8, 5, 4, 3, 2, 1, 100, 50, 17};

      for(i = 0; i < sizeof(a)/ sizeof(int); ++i)
      {
            KeyValue *kv = key_value_new(a[i], NULL);
            priority_queue_enqueue(pq, kv); 
      }

      priority_queue_print(pq);
      priority_queue_free(pq, NULL);

      system("pause");
      return 0;
}


Related articles: