home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / pctchnqs / 1991 / number2 / heap.cpp < prev    next >
C/C++ Source or Header  |  1991-04-02  |  3KB  |  101 lines
  1. // ==========================================================
  2. // Listing 2: heap.cpp
  3. // C++ code implementing binary heaps.
  4. // Copyright (C) 1991 by Nicholas Wilt.  All rights reserved.
  5. // ==========================================================
  6. // Refer to the MAKEFILE listing (Listing 4) for dependencies
  7. // ----------------------------------------------------------
  8.  
  9. #include <alloc.h>
  10. #include "heap.h"
  11.  
  12. // --------------------------------------------------------------
  13. // Constructor:  Takes a pointer to a comparison function akin to
  14. //               those used by bsearch() and qsort().
  15. // --------------------------------------------------------------
  16. Heap::Heap(int (*ComparisonFunction)(void *, void *))
  17. {
  18.   elms = (void **) malloc(DEFSIZE * sizeof(void *));
  19.   n = 0;
  20.   maxsize = DEFSIZE;
  21.   comp = ComparisonFunction;
  22. }
  23.  
  24. // --------------------------------------------------------------
  25. // Destructor:    Free the allocated memory.
  26. // --------------------------------------------------------------
  27. Heap::~Heap()
  28. {
  29.   free(elms);
  30. }
  31.  
  32. // --------------------------------------------------------------
  33. // SiftUp(): Restores the heap property if broken at the bottom.
  34. // --------------------------------------------------------------
  35. void Heap::SiftUp()
  36. {
  37.   int i = n - 1;
  38.  
  39.   while (i) {
  40.     int p = (i-1) >> 1;
  41.     void *temp;
  42.     if ((*comp)(elms[p], elms[i]) <= 0)
  43.       break;
  44.     temp = elms[i];
  45.     elms[i] = elms[p];
  46.     elms[p] = temp;
  47.     i = p;
  48.   }
  49. }
  50.  
  51. // --------------------------------------------------------------
  52. // SiftDown(): Restores the heap property if broken at the top.
  53. // --------------------------------------------------------------
  54. void Heap::SiftDown()
  55. {
  56.   int i = 0;
  57.   int c;
  58.  
  59.   while ( (c = i+i+1) < n) {
  60.     void *temp;
  61.     if (c+1 < n)
  62.       c += ((*comp)(elms[c+1], elms[c]) < 0);
  63.       if ((*comp)(elms[i], elms[c]) <= 0)
  64.     break;
  65.       temp = elms[i];
  66.       elms[i] = elms[c];
  67.       elms[c] = temp;
  68.       i = c;
  69.   }
  70. }
  71.  
  72. // --------------------------------------------------------------
  73. // Insert(): Insert an element into the heap and restore the heap
  74. //           property.
  75. // --------------------------------------------------------------
  76. void Heap::Insert(void *ptr)
  77. {
  78.   if (++n >= maxsize) {
  79.     maxsize <<= 1;
  80.     elms = (void **) realloc(elms, maxsize * sizeof(void *));
  81.   }
  82.   elms[n-1] = ptr;
  83.   SiftUp();
  84. }
  85.  
  86. // --------------------------------------------------------------
  87. // Extract(): Extract the ranking element from the heap and
  88. //            restore the heap property.
  89. // --------------------------------------------------------------
  90. void *Heap::Extract()
  91. {
  92.   void *ret;
  93.  
  94.   if (! n)
  95.     return 0;
  96.   ret = elms[0];
  97.   elms[0] = elms[--n];
  98.   SiftDown();
  99.   return ret;
  100. }
  101.