// heap.cc   ADT for a min-heap   P. Conrad CISC220 06J

#include "heap.h"


Heap_C::Heap_C() // create empty heap
{
  count = 0;
}

void Heap_C::add(int x) // O(log n)
{
  data[count] = x;
  count ++;
  bubbleUp(count-1); 
}

int Heap_C::deleteMin() // O(log n)
{
  int result = data[0];
  data[0] = data[count -1];
  count --;
  heapify(0);
  return result;
}

void Heap_C::bubbleUp(int index)
{
  // move up towards the root

  // check whether this element is already <= to its parent.
  // if we are at the root, it's parent is "itself", so this 
  // will succeed.   If we are already <= to the parent, this is the
  // base case and we are finished

  int parent = parentOf(index);

  if (data[parent] <= data[index] )
    return; // base case

  // otherwise, swap the two and do a recursive call on the parent

  // swap the root of this subtree with the smaller child

  int temp = data[parent];
  data [parent] = data[index];
  data [index] = temp;

  bubbleUp(parent);
  

}


void Heap_C::heapify(int index)
{

  // @@@ THIS CODE IS WRONG---WHY????

  // we will need to compute these values several times,
  // so storing them in a local variable is both 
  // more efficient (in terms of CPU) and 
  // make the code easier to read

  int leftChild = leftChildOf(index);
  int rightChild = rightChildOf(index);

  // check the node at position "index".
  // see if it is smaller than the two children.
  // If so, we can just return--that is the base case
  
  if ( data[index] <= data[leftChild] && data[index] <= data[rightChild]  )
  {
    return;
  }

  // recursive call: pull up the smaller of the two children,
  // then do a recursive call on whichever one we swapped with


  int smallerChild = leftChild; // assume leftChild is smaller

  if ( data[rightChild] <= data[leftChild] )
    smallerChild = rightChild; // change if our assumption was wrong

  // swap the root of this subtree with the smaller child

  int temp = data[smallerChild];
  data [smallerChild] = data[index];
  data [index] = temp;

  // do a recursive call on the tree we swapped with 
  // in case the value we placed there is still larger than ITS children

  heapify(smallerChild);

}



#include "runTests.h"

void Heap_C::testPrivateMemberFunctions(RunTests_C &test)
{
  test.assertEquals(parentOf(0),0);
  test.assertEquals(parentOf(1),0);
  test.assertEquals(parentOf(2),0);
  test.assertEquals(parentOf(3),1);
  test.assertEquals(parentOf(4),1);
  test.assertEquals(parentOf(5),2);
  test.assertEquals(parentOf(6),2);
  test.assertEquals(parentOf(7),3);
  test.assertEquals(parentOf(8),3);

  test.assertEquals(leftChildOf(0),1);
  test.assertEquals(rightChildOf(0),2);
  test.assertEquals(leftChildOf(1),3);
  test.assertEquals(rightChildOf(1),4);
  test.assertEquals(leftChildOf(2),5);
  test.assertEquals(rightChildOf(2),6);
  test.assertEquals(leftChildOf(3),7);
  test.assertEquals(rightChildOf(3),8);


}