// Binary heap routines - root (at subscript 1) has minimum.
// Also supports handle array for linking from another data structure.
// handle[i] gives the heap subscript for the entry with
// id number i.  (Also, handle[heap[j].id]==j . . .).

#include <iostream>
#include <stdlib.h>
#include "minHeap.h"

using namespace std;

bool minHeap::full()
// Is this heap full?
{
  return n==maxSub;
}

bool minHeap::empty()
// Is this heap empty?
{
  return n==0;
}

void minHeap::heapify(int j)
{
// The subtrees to the left and right of heap[j] must have
// the minHeap property.  At completion of this routine, the
// entire subtree rooted at heap[j] will have the minHeap
// property.
int best,r;
heapEntryType entry=heap[j];

while (1)
{
  // Find child with smaller priority
  best=LEFT(j);
  if (best>n)
    break;  // Gone past the leaves

  r=RIGHT(j);
  // Does left or right child have the smaller priority?
  if (r<=n && heap[best].priority>heap[r].priority)
    best=r;
  if (entry.priority<=heap[best].priority)
    break;  // minHeap property holds in subtree

  // Move best child to parent
  heap[j]=heap[best];
  handle[heap[j].id]=j;
  // Continue rippling one level deeper.
  // Again, the left and right subtrees have the minHeap property.
  j=best;
}
// Drop off item from root of subtree (original j)
heap[j]=entry;
handle[heap[j].id]=j;
}

void minHeap::swapUp(int j)
{
// Ancestors of heap[j] have the minHeap property,
// so fixing the heap is a matter of having heap[j]
// climb past its ancestors with larger priorities.
int p;
heapEntryType entry=heap[j];

p=PARENT(j);
while (p>=1 && heap[p].priority>entry.priority)
{
  heap[j]=heap[p];
  handle[heap[j].id]=j;
  j=p;
  p=PARENT(j);
}

// Drop off item with new priority
heap[j]=entry;
handle[heap[j].id]=j;
}

int minHeap::getPriority(int id)
{
if (id<0 || id>=maxSub || handle[id]==(-1))
{
  cout << "id " << id << " issue for getPriority " << __LINE__ << "\n";
  exit(0);
}

return heap[handle[id]].priority;
}

void minHeap::changePriority(heapEntryType iEntry)
{
// Changes priority of item iId to iPriority
int i=handle[iEntry.id];

if (iEntry.priority>heap[i].priority)
{
  // New priority is larger, so slide down
  heap[i].priority=iEntry.priority;
  heapify(i);
}
else
{
  // New priority is smaller, so swap up
  heap[i].priority=iEntry.priority;
  swapUp(i);
}
}

void minHeap::insert(heapEntryType iEntry)
// Insert a new heap entry. 
{
int j;

if (full())
{
  cout << "Heap table size exceeded!"<< __LINE__ << "\n";
  exit(0);
}

if (iEntry.id<0 || iEntry.id>=maxSub || handle[iEntry.id]!=(-1))
{
  cout << "id " << iEntry.id << " issue for insert " << __LINE__ << "\n";
  exit(0);
}

j=(++n);  // Put next item into use

// Swap the new item up the heap
heap[j]=iEntry;
swapUp(j);
}

void minHeap::deleteId(int id)
// Deletes the entry for id and frees its handle.
{
heapEntryType work;
int heapSlot,donor;

if (id<0 || id>=maxSub || handle[id]==(-1))
{
  cout << "id " << id << " issue for delete " << __LINE__ << "\n";
  exit(0);
}
heapSlot=handle[id];
handle[id]=(-1);
donor=(n--);         // Last leaf element gets moved
if (donor==heapSlot)
  return;

// Next two lines transform the donation into a change of priority.
heap[heapSlot].id=heap[donor].id;
handle[heap[heapSlot].id]=heapSlot;
changePriority(heap[donor]);
}

heapEntryType minHeap::minimum()
// Returns minimum element, but leaves it in the heap.
{
if (empty())
{
  cout << "Heap empty!"<< __LINE__ << "\n";
  exit(0);
}

return heap[1];
}

heapEntryType minHeap::extractMin()
{
heapEntryType returnEntry;

if (empty())
{
  cout << "Heap empty!"<< __LINE__ << "\n";
  exit(0);
}

// Values being returned
returnEntry=heap[1];
handle[heap[1].id]=(-1); // Invalidate handle

n--;  // Item is taken out of use
if (empty())
  return returnEntry;

// Last item (at highest-subscripted leaf) becomes the root and slides down.
heap[1]=heap[n+1];
heapify(1);
return returnEntry;
}

minHeap::minHeap(int capacity)
{
heap=new heapEntryType[capacity+1];
handle=new int[capacity];

if (!heap || !handle)
{
  cout << "new failed!"<< __LINE__ << "\n";
  exit(0);
}
// Invalidate handles
for (int i=0;i<capacity;i++)
  handle[i]=(-1);
maxSub=capacity+1;
n=0;
}

minHeap::minHeap(int capacity,int priorityIn[],int count)
{
int i;

heap=new heapEntryType[capacity+1];
handle=new int[capacity];
if (!heap || !handle)
{
  cout << "new failed!"<< __LINE__ << "\n";
  exit(0);
}
maxSub=capacity+1;
n=count;
// Caller should know conventions for ids and handles.
for (i=0;i<count;i++)
{
  heap[i+1].priority=priorityIn[i];
  heap[i+1].id=i;
  handle[i]=i+1;
}
// Invalidate unused handles
for ( ;i<capacity;i++)
  handle[i]=(-1);

// Sliding down starting from each node that is a parent,
// in descending subscript (not priority) order.
for (i=PARENT(n);i>0;i--)
  heapify(i);
}

minHeap::minHeap()
{
minHeap(50);
}

minHeap::~minHeap()
{
delete [] heap;
delete [] handle;
}