Issue 11: Error in removing the first element from the binary heap
Status:  Fixed
Owner:
Closed:  Feb 2012
Project Member Reported by J.Wes.Pickens, Feb 14, 2012
Implemented a binary heap and it passed initial unit tests; however, I'm getting an error when I now try to run acceptance tests...

Traceback (most recent call last):
  File "RunPFD.py", line 13, in <module>
    pfd_solve(sys.stdin, sys.stdout)
  File "D:\My Documents\Dropbox\School Stuff\CS 373\workspace\PFD\PFD.py", line 179, in pfd_solve
    s = pfd_sort(a, vertices)
  File "D:\My Documents\Dropbox\School Stuff\CS 373\workspace\PFD\PFD.py", line 78, in pfd_sort
    binHeapRemoveFirst(noDependencies)
  File "D:\My Documents\Dropbox\School Stuff\CS 373\workspace\PFD\PFD.py", line 139, in binHeapRemoveFirst
    if binHeap[child1] > binHeap[index] :
IndexError: list index out of range
Feb 14, 2012
Project Member #1 J.Wes.Pickens
It looks like the problem is when performing the down-heap, the element being moved down the heap gets to a point where it's not the last element, but it's close enough to the end that its children at (index * 2) + 1 and (index * 2) + 2 are out of bounds.

Need to deal with that special case.
Feb 14, 2012
Project Member #2 J.Wes.Pickens
(No comment was entered for this change.)
Summary: Error in removing the first element from the binary heap
Feb 14, 2012
Project Member #3 J.Wes.Pickens
The case where the element has no children should be handled the same as if it had reached the last element in the heap.

The special case to be addressed is when the element has only one child.
Feb 14, 2012
Project Member #4 J.Wes.Pickens
Added code to address the special cases.  Able to run acceptance tests without compilation errors.
Status: Fixed