Systemnahe Programmierung in Chome Systemnahe Programmierung in C: Vorrang-Warteschlangen Prof. Dr. Uwe Schmidt FH Wedel
Dynamische Datenstrukturen
Binäre Patricia-BäumeInhaltsverzeichnisHashtabellen

Vorrang-Warteschlangen

weiter
weiter

Implementierung Vorrang-Warteschlangen (priority queues) mit einem binären Baum (binary heap)

Vorrang-Warteschlangen
werden zur Speicherung beliebig vieler Elemente oder Schlüssel-Wert-Paare verwendet, wobei nur der schnelle Zugriff auf das kleinste Element aus einer Menge gefordert wird. Das effiziente Suchen eines beliebigen Elements ist nicht gefordert.
 
Eine einfache Implementierung ist die mit einer linearen Liste mit Sortierung und Duplikaten. Bei dieser Implementierung dauert der Zugriff auf das kleinste Element (auf den Kopf der Liste) konstant lange, aber das Einfügen läuft mit O(n) mit n = #Elemente in der Liste.
 
Mit binären Bäumen ist eine Laufzeit für das Einfügen und Löschen von O(log n) möglich.
 
Die Datentypen sind genau die gleichen wie bei binären Suchbäumen.
 
Diese Datenstruktur kann auch zum effizienten Sortieren verwendet werden.
weiter
weiter

Die Schnittstelle: Element.h

   1#ifndef ELEMENT_H__
   2#define ELEMENT_H__ 1
   3
   4typedef char *Element;
   5
   6extern int compare(Element e1,
   7                   Element e2);
   8
   9#endif
weiter
weiter

Die Implementierung: Element.c

   1#include "Element.h"
   2#include <string.h>
   3
   4int
   5compare (Element e1, Element e2)
   6{
   7  int rel = strcmp (e1, e2);
   8
   9  return (rel > 0) - (rel < 0);
  10}
weiter
weiter

Die Schnittstelle: Heap.h

   1#ifndef HEAP_H__
   2#define HEAP_H__
   3
   4/* usage:
   5   the type "Element" for the elements
   6   to be stored must be declared elsewere
   7   this type must support a compare function
   8   like strcmp, with results -1,0,+1
   9   reflecting the ordering relation
  10
  11   see "Element.h" and "Element.c" examples
  12*/
  13
  14typedef struct Node *Heap;
  15
  16struct Node
  17{
  18  Element info;
  19  Heap l;
  20  Heap r;
  21};
  22
  23extern Heap mkEmptyHeap(void);
  24extern Heap mkOneElemHeap(Element e);
  25
  26extern int isEmptyHeap(Heap h);
  27extern Element minElem(Heap h);
  28
  29extern Heap deleteMinElem(Heap h);
  30extern Heap insertElem(Element e, Heap h);
  31extern Heap mergeHeaps(Heap h1, Heap h2);
  32
  33extern int invHeap(Heap h1);
  34
  35#endif
weiter
weiter

Die Implementierung: Heap.c

   1#include "Heap.h"
   2
   3#include <stdlib.h>
   4#include <stdio.h>
   5#include <assert.h>
   6
   7/*--------------------*/
   8
   9Heap
  10mkEmptyHeap (void)
  11{
  12  return (Heap) 0;
  13}
  14
  15#if MACROS
  16#define mkEmptyHeap() ((Heap)0)
  17#endif
  18
  19/*--------------------*/
  20
  21Heap
  22mkOneElemHeap (Element e)
  23{
  24  Heap res = malloc (sizeof (*res));
  25
  26  if (!res)
  27    {
  28      perror ("mkOneElemHeap: malloc failed");
  29      exit (1);
  30    }
  31  res->info = e;
  32  res->l = mkEmptyHeap ();
  33  res->r = mkEmptyHeap ();
  34
  35  return res;
  36}
  37
  38/*--------------------*/
  39
  40int
  41isEmptyHeap (Heap s)
  42{
  43  return s == (Heap) 0;
  44}
  45
  46#if MACROS
  47#define isEmptyHeap(s) ((s) == (Heap)0)
  48#endif
  49
  50/*--------------------*/
  51
  52Element
  53minElem (Heap h)
  54{
  55  assert (!isEmptyHeap (h));
  56
  57  return h->info;
  58}
  59
  60#if MACROS
  61#define minElem(h) ((h)->info)
  62#endif
  63
  64/*--------------------*/
  65
  66Heap
  67deleteMinElem (Heap h)
  68{
  69  assert (!isEmptyHeap (h));
  70
  71  {
  72    Heap res = mergeHeaps (h->l, h->r);
  73    free(h);
  74    return res;
  75  }
  76}
  77
  78/*--------------------*/
  79
  80Heap
  81insertElem (Element e, Heap h)
  82{
  83  return mergeHeaps (mkOneElemHeap (e), h);
  84}
  85
  86/*--------------------*/
  87
  88static Heap
  89joinHeaps (Heap h1, Heap h2)
  90{
  91  Heap t;
  92
  93  assert (!isEmptyHeap (h1));
  94  assert (!isEmptyHeap (h2));
  95  assert (compare (h1->info, h2->info) <= 0);
  96
  97  t = mergeHeaps (h1->l, h2);
  98  h1->l = h1->r;
  99  h1->r = t;
 100
 101  return h1;
 102}
 103
 104/*--------------------*/
 105
 106Heap
 107mergeHeaps (Heap h1, Heap h2)
 108{
 109  if (isEmptyHeap (h1))
 110    return h2;
 111
 112  if (isEmptyHeap (h2))
 113    return h1;
 114
 115  if (compare (minElem (h1), minElem (h2)) <= 0)
 116    return joinHeaps (h1, h2);
 117
 118  return joinHeaps (h2, h1);
 119}
 120
 121/*--------------------*/
 122
 123static int
 124greaterThanOrEqual (Heap h, Element e)
 125{
 126  return 
 127    isEmptyHeap (h)
 128    ||
 129    ( compare (h->info, e) >= 0 );
 130}
 131
 132int
 133invHeap (Heap h)
 134{
 135  return
 136    isEmptyHeap (h)
 137    ||
 138    (greaterThanOrEqual (h->l, h->info)
 139     &&
 140     greaterThanOrEqual (h->r, h->info)
 141     &&
 142     invHeap(h->l)
 143     &&
 144     invHeap(h->r)
 145     );
 146}
 147
 148/*--------------------*/
weiter
weiter

Ein Testprogramm: main.c

   1#include <stdio.h>
   2#include <stdlib.h>
   3
   4typedef long int Element;
   5
   6int
   7compare (Element e1, Element e2)
   8{
   9  return (e1 >= e2) - (e1 <= e2);
  10}
  11
  12#if LINKEDLIST
  13
  14#define SORTED 1
  15#define ITERATIVE 1
  16
  17#include "List.c"
  18
  19/* rename functions */
  20#define Heap List
  21
  22#define mkEmptyHeap() mkEmptyList()
  23#define mkOneElemHeap(e) cons(e,mkEmptyList())
  24#define isEmptyHeap(h) isEmptyList(h)
  25#define minElem(h) head(h)
  26#define deleteMinElem(h) removeHead(h)
  27#define insertElem(e,h) addElem(e,h)
  28
  29#else
  30
  31#include "Heap.c"
  32
  33#endif
  34
  35#if TRACE
  36#define trace(s) s
  37#else
  38#define trace(s)
  39#endif
  40
  41static Heap addElems (unsigned n, Heap h);
  42static Heap delElems (unsigned n, Heap h);
  43
  44int
  45main (int argc, char *argv[])
  46{
  47
  48  unsigned int card = 1000;     /* max size of heap */
  49  if (argc == 2)
  50    sscanf (argv[1], "%u", &card);
  51
  52  trace (
  53    fprintf (stderr,
  54             "run priority queue test with %u elements\n",
  55             card));
  56
  57  {
  58    Heap h = mkEmptyHeap ();
  59    h = addElems (card, h);
  60    h = delElems (card, h);
  61
  62    trace (
  63      fprintf (stderr,
  64               "test finished %s\n",
  65               isEmptyHeap (h)
  66               ? "successfully"
  67               : "with failure"));
  68
  69    return !isEmptyHeap (h);
  70  }
  71}
  72
  73
  74Heap
  75addElems (unsigned n, Heap h)
  76{
  77  trace (
  78    fprintf (stderr,
  79             "insert %u random elements\n",
  80             n));
  81
  82  while (n--)
  83    {
  84      Element e = random ();
  85      trace (
  86        fprintf (stderr,
  87                 "%12ld\n",
  88                 e));
  89
  90      h = insertElem (e, h);
  91
  92    }
  93  return h;
  94}
  95
  96Heap
  97delElems (unsigned n, Heap h)
  98{
  99  trace (
 100    fprintf (stderr,
 101             "delete %u elements\n",
 102             n));
 103
 104  while (n--)
 105    {
 106      trace (
 107        fprintf (stderr,
 108                 "%12ld\n",
 109                 minElem (h)));
 110
 111      h = deleteMinElem (h);
 112    }
 113  return h;
 114}
weiter
weiter

Ein Makefile für die Erzeugung der Test-Varianten: Makefile

SOURCES = main.c Heap.h Heap.c List.h List.c Makefile
HEAPSIZE = 1000000
all : heapTest traceTest profTest \
linkedlistTest optprofTest
heapTest : $(SOURCES)
cc -o $@ -DTRACE=0 -DNDEBUG=1 main.c
profTest : $(SOURCES)
cc -o $@ -pg -DTRACE=0 -DNDEBUG=1 main.c
optprofTest : $(SOURCES)
cc -o $@ -pg -DTRACE=0 -DNDEBUG=1 -DMACROS=1 main.c
traceTest : $(SOURCES)
cc -o $@ -DTRACE=1 main.c
linkedlistTest : $(SOURCES)
cc -o $@ -DTRACE=0 -DNDEBUG=1 -DLINKEDLIST=1 main.c
test1 : traceTest
./traceTest 100
test2 : heapTest
echo "priority queue with binary heap test :" \
"$(HEAPSIZE) elements"
/usr/bin/time --format="runtime was %U sec" \
./heapTest $(HEAPSIZE)
test3 : profTest
echo "priority queue with binary heap test :" \
"$(HEAPSIZE) elements (profile version)"
rm -f gmon.out
./profTest $(HEAPSIZE)
gprof --brief profTest gmon.out
test3a : optprofTest
echo "priority queue with binary heap test :" \
"$(HEAPSIZE) elements (profile optimized version)"
rm -f gmon.out
./optprofTest $(HEAPSIZE)
gprof --brief optprofTest gmon.out
test4 : linkedlistTest
echo "priorty queue with sorted linked list test :" \
"$(HEAPSIZE) elements"
/usr/bin/time --format="runtime was %U sec" \
./linkedlistTest $(HEAPSIZE)
10k 20k 100k 200k 500k 1M 2M :
$(MAKE) test2 \
HEAPSIZE=`echo $@ | sed -e 's|k|000|' -e 's|M|000000|'`
l10k l20k l30k l40k l50k l100k l200k l500k l1M l2M :
$(MAKE) test4 \
HEAPSIZE=`echo $@ | sed -e 's|^l||g' -e 's|k|000|' -e 's|M|000000|'`
p10k p100k p200k p500k p1M p2M :
$(MAKE) test3 \
HEAPSIZE=`echo $@ | sed -e 's|^p||g' -e 's|k|000|' -e 's|M|000000|'`
o10k o100k o200k o500k o1M o2M :
$(MAKE) test3a \
HEAPSIZE=`echo $@ | sed -e 's|^o||g' -e 's|k|000|' -e 's|M|000000|'`
clean :
rm -f *.o *Test
weiter
weiter

Test mit Trace-Ausgabe

make -s test1
weiter
weiter

Test mit Zeitmessung für 10.000 Elemente

make -s 10k
weiter
weiter

Test mit Zeitmessung für 100.000 Elemente

make -s 100k
weiter
weiter

Test mit Zeitmessung für 1.000.000 Elemente

make -s 1M
weiter
weiter

Test mit Profiling für 1.000.000 Elemente

make -s p1M
weiter
weiter

Test mit Makros und Profiling für 1.000.000 Elemente

make -s o1M
weiter
weiter

Test mit sortierter verketteter Liste für 10.000 Elemente

make -s l10k
weiter
weiter

Test mit sortierter verketteter Liste für 20.000 Elemente

make -s l20k
weiter
weiter

Test mit sortierter verketteter Liste für 30.000 Elemente

make -s l30k
weiter
weiter

Download

Quellen
Element.h
Element.c
Heap.h
Heap.c
List.h
List.c
main.c
Makefile
SeitenanfangDynamische Datenstrukturen
Binäre Patricia-BäumeInhaltsverzeichnisHashtabellen
Letzte Änderung: 15.01.2013
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel