2016-05-04

posted May 4, 2016, 8:22 AM by Samuel Konstantinovich   [ updated May 4, 2016, 8:55 AM ]
May the 4th be with you.

Update: If you submit your BST without remove you will get full credit. 
If you get remove to work correctly (on time), you will get extra credit.

Goal: One heaping helping of data structures.

Heaps are binary tree like structure

Restrictions when creating heaps:

  1. Parent must always be bigger(max heap) / smaller(min heap) than both children.

  2. tree must always be full ( the tree should be filled from bottom left to right )

Ex: max heap

50

49 40

    a           b         c          d

it would be filled starting from a to b to c then d



get max  = O(1)

add/remove root = O(logn)

add - 1) put the value in the next open spot

         2) push up the value




Remove the root:

1) replace the root with the lower right node (bottom row rightmost node)

2) push it down into the correct place.


Note, the Next position: the lower right most empty spot.

Add a value:

1)The first add makes the value the root

2) puts the new value in the to the next position and checks if the new element is in the correct spot. If not, swap the value with the parent, (repeat) until you have a heap.


Using arrays for heaps

Our array can store the values of the heap like this:

1(Put the value here into index 1)

2 3(put the value here into index 3)

    4      5        6       7

8 9  10 11 12 13  14 15


Notice there is no ‘0’ because doing it this way is much nicer. If we stored int then we could use index 0 as the size variable.


  • 2 * index = left child

  • 2 * index + 1 = right child

  • index / 2 = parent index

  • index 0 used for counter of elements


Example:

a

b c

would become an array:

null a b c

Comments