Demo Code

pqueue-binomial-heap.cpp

// This is the .cpp file for the binomial heap implementation of a 
// Priority Queue, demonstrates some pointer work. All code on this
// page is mine.
// http://www.stanford.edu/class/cs106x/handouts/26-Assignment-4-PQueue.pdf

#include "pqueue-binomial-heap.h"

BinomialHeapPQueue::BinomialHeapPQueue() 
{
    logSize = 0;
}
BinomialHeapPQueue::~BinomialHeapPQueue() 
{
    recursiveDestroy(heap);
}

// Recursively deallocates all of the nodes in the heap.
void BinomialHeapPQueue::recursiveDestroy(Vector<node*> &nodes)
{
    foreach(node* n in nodes)
    {
        if(n == NULL) continue;
        recursiveDestroy(n->children);
        delete n;
    }
}

// Returns the minimum value without removing it.
string BinomialHeapPQueue::peek() 
{
    string min = "";
    foreach(node* n in heap) if(min == "" || n->value.compare(min) < 0) min = n->value;
	return min;
}

// Removes the smallest element and then reenques all of its children.
string BinomialHeapPQueue::extractMin() 
{
    if(logSize == 0) return "";
    int mindex = 0;
    string min = "";
    for(int i = 0; i < heap.size(); i++)
    {
        if(heap[i] != NULL && (heap[i]->value.compare(min) < 0 || min == ""))
        {
            mindex = i;
            min = heap[i]->value;
        }
    }
    node* oldNode = heap[mindex];
    heap[mindex] = NULL;
    purify(heap);
    BinomialHeapPQueue* pq = new BinomialHeapPQueue;
    for(int i = 0; i < oldNode->children.size(); i++) pq->heap.add(oldNode->children[i]);
    heap = merge(this, pq)->heap;
    logSize--;
    delete oldNode;
    return min;
}

// Create a newheap containing only the elem and merges it with itself.
void BinomialHeapPQueue::enqueue(string elem) 
{
    BinomialHeapPQueue* newheap = new BinomialHeapPQueue;
    Vector<node*> newvect;
    node* newnode = new node;
    newnode->value = elem;
    newnode->children = newvect;
    newheap->heap.add(newnode);
    newheap->logSize++;
    heap = merge(this, newheap)->heap;
    logSize++;
}


// Removes trailing NULL values. This does not recur for all the children because
// children will never accrue trailing NULL values because the only operations
// performed on them are additions of nodes with values.
void BinomialHeapPQueue::purify(Vector<node*> &nodes)
{
    int i = nodes.size()-1;
    while(i > 0)
    {
        if(nodes[i] != NULL) break;
        nodes.removeAt(i);
        i = nodes.size()-1;
    }
}

// Returns a BinomialHeapPQueue pointer representing the two inputs merged.
BinomialHeapPQueue *BinomialHeapPQueue::merge(BinomialHeapPQueue *one, BinomialHeapPQueue *two) 
{
    one->purify(one->heap);
    two->purify(two->heap);
    BinomialHeapPQueue* merge = new BinomialHeapPQueue;
    merge->logSize = one->logSize+two->logSize;
    node* carry = NULL;
    int onesize = one->heap.size();
    int twosize = two->heap.size();
    for(int i = 0; i < ((onesize > twosize) ? onesize : twosize)+1; i++)
    {
        Vector<node*> possibleNodes;
        if(carry != NULL) possibleNodes.add(carry);
        carry = NULL;
        if(one->heap.size() > i && one->heap[i] != NULL) possibleNodes.add(one->heap[i]);
        if(two->heap.size() > i && two->heap[i] != NULL) possibleNodes.add(two->heap[i]);
        if(possibleNodes.size() >= 2)
        {
            node* larger = ((possibleNodes[0]->value.compare(possibleNodes[1]->value) > 0) 
                            ? possibleNodes[0] : possibleNodes[1]); // Larger of first two elements in possibleNodes
            node* smaller = ((possibleNodes[0]->value.compare(possibleNodes[1]->value) <= 0) 
                             ? possibleNodes[0] : possibleNodes[1]); // Smaller of first two elements in possibleNodes
            smaller->children.add(larger);
            carry = smaller;
            if(possibleNodes.size() == 3) merge->heap.add(possibleNodes[2]);
            else merge->heap.add(NULL);
        }
        else if(possibleNodes.size() == 1) merge->heap.add(possibleNodes[0]);
        else merge->heap.add(NULL);
    }
    merge->purify(merge->heap);
    return merge;
}

pqueue-binomial-heap.h

// Here's the corresponding header file for binomial heap. Not all code on this page is mine.
// http://www.stanford.edu/class/cs106x/handouts/26-Assignment-4-PQueue.pdf

/**
 * pqueue-binomial-heap.h
 * priority-queue
 *
 * Created by Jerry Cain on 10/23/10.
 * Modified by Douglas Safreno.
 * Copyright 2010 Stanford University. All rights reserved.
 */

#ifndef __binomial_heap_pqueue_cs106__
#define __binomial_heap_pqueue_cs106__

#include "pqueue.h"
#include "Vector.h"

class BinomialHeapPQueue : public PQueue {
public:
	BinomialHeapPQueue();
	~BinomialHeapPQueue();
	
	static BinomialHeapPQueue *merge(BinomialHeapPQueue *one, BinomialHeapPQueue *two);
	
	void enqueue(string elem);
	string extractMin();
	string peek();
	
private:
    struct node
    {
        string value;
        Vector<node*> children;
    };
    Vector<node*> heap;
    void purify(Vector<node*> &heap);
    void recursiveDestroy(Vector<node*> &heap);
    node* merge(node* one, node* two);
};
#endif

pqueue-heap.cpp

// This is the .cpp file for the regular heap implementation of a 
// Priority Queue, demonstrates some pointer work this without vectors. 
// All code on this page is mine.
// http://www.stanford.edu/class/cs106x/handouts/26-Assignment-4-PQueue.pdf


#include "pqueue-heap.h"

HeapPQueue::HeapPQueue() 
{
    heapSize = 10;
    heap = new string[heapSize];
    logSize = 0;
}
HeapPQueue::~HeapPQueue() 
{
    delete[] heap;
}

// Returns the minimum value without removing it from the heap.
string HeapPQueue::peek() 
{ 
    if(logSize == 0) return "";
    return heap[0];
	return "";
}

// Removes the minimum value from the heap, moves the last value in the heap to the top,
// and then moves it down the heap by swapping with smaller values until it reaches its
// proper place. This reorders the heap.
string HeapPQueue::extractMin() 
{
    if(logSize == 0) return "";
    string val = heap[0];
    heap[0] = heap[logSize-1];
    int i = 0;
    logSize--;
    while(true)
    {
        if(2*i+1 >= logSize) break;
        if(heap[i].compare(heap[2*i]) <= 0 && heap[i].compare(heap[2*i+1]) <= 0) break; 
        if(heap[2*i].compare(heap[2*i+1]) < 0) 
        {
            heapSwap(i, 2*i);
            i = 2*i;
        }
        else 
        {
            heapSwap(i, 2*i+1);
            i = 2*i+1;
        }
    }
    if(2*i+1 == logSize && heap[2*i].compare(heap[i]) < 0) heapSwap(i, 2*i);
    return val;
}

// Adds the elem to the heap ensuring that it arrives in the proper location.
void HeapPQueue::enqueue(string elem) 
{
    if(logSize == 0)
    {
        heap[0] = elem;
        logSize++;
        return;
    }
    if(heapSize == logSize) biggerHeap();
    heap[logSize] = elem;
    int curr = logSize;
    int halfCurr = curr/2;
    while(curr > 0)
    {
        if(heap[curr].compare(heap[halfCurr]) < 0) heapSwap(curr, halfCurr);
        else break;
        curr = halfCurr;
        halfCurr /= 2;
    }
    logSize++;
}

// Swaps the location in the heap at the two given indeces.
void HeapPQueue::heapSwap(int i1, int i2)
{
    string temp = heap[i1];
    heap[i1] = heap[i2];
    heap[i2] = temp;
}

// Increases the size of the heap.
void HeapPQueue::biggerHeap()
{
    heapSize *= HEAP_MULTIPLIER;
    string* temp = new string[heapSize];
    for(int i = 0; i < logSize; i++) temp[i] = heap[i];
    heap = temp;
}

// Moves the element into its proper location in the heap
void HeapPQueue::heapify(int loc)
{
    if(2*loc+1 >= logSize) return;
    if(heap[loc].compare(heap[2*loc]) > 0 || heap[loc].compare(heap[2*loc+1]) > 0)
    {
        int newloc = heap[2*loc].compare(heap[2*loc+1]) < 0 ? 2*loc : 2*loc+1;
        heapSwap(loc, newloc);
        heapify(newloc);
    }
}

// Creates a new HeapPQueue containing all of the data of one and two.
HeapPQueue *HeapPQueue::merge(HeapPQueue *one, HeapPQueue *two) 
{
    HeapPQueue* merge = new HeapPQueue;
    merge->heapSize = one->heapSize + two->heapSize;
    merge->heap = new string[merge->heapSize];
    for(int i = 0; i < one->logSize; i++)
    {
        merge->heap[i] = one->heap[i];
        merge->logSize++;
    }
    for(int i = 0; i < two->logSize; i++)
    {
        merge->heap[i+one->logSize] = two->heap[i];
        merge->logSize++;
    }
    int tier = 0;
    while((2^tier) < merge->logSize) tier++;
    for(int i = merge->logSize-1; i >= 0; i--) merge->heapify(i);
    return merge;
}

pqueue-heap.h

// Here's the corresponding header file for binomial heap. Not all code on this page is mine.
// http://www.stanford.edu/class/cs106x/handouts/26-Assignment-4-PQueue.pdf

/**
 * pqueue-heap.h
 * priority-queue
 *
 * Created by Jerry Cain on 10/23/10.
 * Copyright 2010 Stanford University. All rights reserved.
 */

#ifndef __binary_heap_pqueue_cs106__
#define __binary_heap_pqueue_cs106__
#define HEAP_MULTIPLIER 2

#include "pqueue.h"

class HeapPQueue : public PQueue {
public:
	HeapPQueue();
	~HeapPQueue();
	
	static HeapPQueue *merge(HeapPQueue *one, HeapPQueue *two);
	
	void enqueue(string elem);
	string extractMin();
	string peek();
	
private:
    void heapify(int loc);
    void heapSwap(int i1, int i2);
    void biggerHeap();
    string* heap;
    int heapSize;
};

#endif