minheap.cpp

经典c++程序的实现

#include <assert.h>
#include <iostream.h>
#include <stdio.h>

#include "..\include\book.h"

typedef int ELEM;

#include "..\include\swap.h"

#include "..\include\minheap.h"

heap::heap(ELEM* h, int num, int max)   // Constructor
  { Heap = h;  n = num;  size = max;  buildheap(); }

int heap::heapsize() const // Return current size of the heap
  { return n; }

bool heap::isLeaf(int pos) const // TRUE if pos is a leaf position
  { return (pos >= n/2) && (pos < n); }

// Return position for left child of pos
int heap::leftchild(int pos) const {
  assert(pos < n/2);  // Must be a position with a left child
  return 2*pos + 1;
}

// Return position for right child of pos
int heap::rightchild(int pos) const {
  assert(pos < (n-1)/2);  // Must be a position with a left child
  return 2*pos + 2;
}

int heap::parent(int pos) const { // Return position for parent
  assert(pos > 0);                // Posmust have a parent
  return (pos-1)/2;
}

void heap::insert(const ELEM val) { // Insert value into heap
  assert(n < size);
  int curr = n++;
  Heap[curr] = val;                 // Start at end of heap
  // Now sift up until curr's parent < curr
  while ((curr!=0) && (key(Heap[curr]) < key(Heap[parent(curr)]))) {
    swap(Heap[curr], Heap[parent(curr)]);
    curr = parent(curr);
  }
}

ELEM heap::removemin() {          // Remove minimum value
  assert(n > 0);
  swap(Heap[0], Heap[--n]); // Swap maximum with last value
  if (n != 0)      // Not on last element
    siftdown(0);   // Put new heap root val in correct place
  return Heap[n];
}

// Remove value at specified position
ELEM heap::remove(int pos) {
  assert((pos > 0) && (pos < n));
  swap(Heap[pos], Heap[--n]); // Swap with last value
  if (n != 0)        // Not on last element
    siftdown(pos);   // Put new heap root val in correct place
  return Heap[n];
}

void heap::buildheap()           // Heapify contents of Heap
  { for (int i=n/2-1; i>=0; i--) siftdown(i); }

void heap::siftdown(int pos) { // Put element in its correct place
  assert((pos >= 0) && (pos < n));
  while (!isLeaf(pos)) {
    int j = leftchild(pos);
    if ((j<(n-1)) && (key(Heap[j]) > key(Heap[j+1])))
      j++; // j is now index of child with greater value
    if (key(Heap[pos]) <= key(Heap[j])) return; // Done
    swap(Heap[pos], Heap[j]);
    pos = j;  // Move down
  }
}