PA2: Heaps

Objectives

The objective of PA2 is to create a heap implementation that is correct and meets the complexity expectations for heap operations. To support you thinking about complexity and evaluating the complexity of your code, we are giving you a framework for measuring the complexity of a heap algorithm: heap_tests.py, includes tests for correct functionality of your code and tests to see if your program's complexity is close to what we expect. The Checkin test program uses heap_tests.py to check your code. You can test your code either using main() in heap.py or calling heap_tests.py. Download starter text:

• heap.txt
• heap_tests.txt

Change heap.txt into heap.py and heap_tests.txt into heap_tests.py. (We call these file x.txt instead of x.py because many browsers refuse to read .py files.) Then follow the instructions in heap.py and implement the required functions. Do not use library functions for the heap operations.

The Checkin tab on the course website will perform preliminary testing of your code. These tests do not indicate your final grade. They can, however, catch mistakes in your submission. You can re-submit your file as often as you want. The Server tests for correctness and complexity. The complexity is measured in terms of swap counts and call counts. Your solution code can have slightly different counts, as long as these are in the proper range (+ OR - 30% of the expected count).
Here is an example run of the main function in heap.py, when executing

  python3 heap.py

the resulting output is:

Complete Tree size 20:
                              20
              28                              26
      24              10              27              21
  12      13      19      15      17      14      29      16
25  18  11  23  22

Heap size 20:
                              10
              11                              14
      12              15              17              16
  18      13      19      28      26      27      29      21
25  20  24  23  22  


REPORT on list of len: 30
buildHeap(A):           	 {'swap_count': 15, 'heapify_call_count': 30}
heapExtractMin(A) => 10:	 {'swap_count': 4, 'heapify_call_count': 5}
heapInsert(A, 10):       	 {'swap_count': 4, 'heapify_call_count': 0}
heapExtractMin(A) => 10:	 {'swap_count': 3, 'heapify_call_count': 4}
heapInsert(A, 1):        	 {'swap_count': 4, 'heapify_call_count': 0}

REPORT on list of len: 400
buildHeap(A):           	 {'swap_count': 287, 'heapify_call_count': 487}
heapExtractMin(A) => 10:	 {'swap_count': 7, 'heapify_call_count': 8}
heapInsert(A, 10):       	 {'swap_count': 8, 'heapify_call_count': 0}
heapExtractMin(A) => 10:	 {'swap_count': 7, 'heapify_call_count': 8}
heapInsert(A, 24):       	 {'swap_count': 4, 'heapify_call_count': 0}

REPORT on list of len: 10000
buildHeap(A):           	 {'swap_count': 7420, 'heapify_call_count': 12420}
heapExtractMin(A) => 10:	 {'swap_count': 13, 'heapify_call_count': 14}
heapInsert(A, 10):       	 {'swap_count': 13, 'heapify_call_count': 0}
heapExtractMin(A) => 10:	 {'swap_count': 12, 'heapify_call_count': 13}
heapInsert(A, 788):       	 {'swap_count': 4, 'heapify_call_count': 0}

REPORT on list of len: 100000
buildHeap(A):           	 {'swap_count': 74571, 'heapify_call_count': 124571}
heapExtractMin(A) => 10:	 {'swap_count': 16, 'heapify_call_count': 17}
heapInsert(A, 10):       	 {'swap_count': 16, 'heapify_call_count': 0}
heapExtractMin(A) => 10:	 {'swap_count': 15, 'heapify_call_count': 16}
heapExtractMin(A) => 11:	 {'swap_count': 16, 'heapify_call_count': 17}
heapExtractMin(A) => 12:	 {'swap_count': 16, 'heapify_call_count': 17}
heapInsert(A, 6311):       	 {'swap_count': 3, 'heapify_call_count': 0}
heapInsert(A, 12418):       	 {'swap_count': 0, 'heapify_call_count': 0}
heapInsert(A, 6890):       	 {'swap_count': 3, 'heapify_call_count': 0}