Weekly Note 6, DM42, fall 2006

Discussion Section October 9

  1. The last proof from the lecture on October 4.
  2. Consider a standard heap. We discuss the deletemin operation which does the following: it removes the root element, takes the currently last element E and places that in the root, and then "bobbles it" down to the correct location. Recall that 2 log n comparisons may be necessary after a deletemin operation (log is base 2). Where does the constant 2 in front of log n come from?

    How quickly (in terms of comparisons) can you find the path to a leaf down which the element E placed in the root will travel? Note that for now you do not have to do any swapping; you only have to identify the path.

    Assume that we store the heap in an array and that the leaf in question is stored in entry x. Which entries in the list does the path mentioned above correspond to, expressed in terms of x?

    Can you now find the correct location for E faster?

    How quickly (in terms of comparisons between elements) can you insert the element into the correct location? What is the total number of comparison for the entire operation?

  3. Double-Ended Priority Queues (pdf)

Lecture October 11


Last modified: Wed Oct 4 15:44:29 CEST 2006
Kim Skak Larsen (kslarsen@imada.sdu.dk)