Algorithmics 2021/22 fall

HW5. Heaps (4th of Oct, 23.59)

Hint: Here Tasks 1-5 do not require implementations. But if you are tempted to, then that's ok as well.

EX1. Binary min heap and binomial heap -- use the data (generated by the generator) from the bottom of the page and simulate insertion, delete-min, and decrease-key operations based on that data. Manual simulation on paper should likely do it, but if it gets too big then simply outline the procedure how the rest should be handled ...

EX2. Give an approximate memory space consumption of a binomial heap of 1 million values. How much memory does it take to store priorities (int), keys (reference to key, key is a string), pointers (within heap), and external links (to and back from keys in dictionary)? References to keys are needed to identify the keys within the priority queue (when not accessed by priority only). How would the 'decrease_priority(key,new_priority)' update work?

EX3. Read: Kamp (CACM 2010 53:7) "You're doing it all wrong.". What is the main criticism in the article? What is your opinion about the article?

EX4. Simulate the binary heap with the CACM article indexing scheme, using the same data as used for Task 1.

EX5. Build d-ary heaps (https://en.wikipedia.org/wiki/D-ary_heap) with the same data of Task 1 for d=5. Describe what are the benefits and which of the three types of heaps you would prefer yourself the most. Why?

Hint: For EX6 and EX7 hopefully you can borrow some ideas for generating data with variable properties (nr of keys, frequency and magnitude of decrease key operations, frequency of delete-min, etc). An alternative example task could be the Heap-Sort.

EX6. Bonus (2p): Modify the data generator to work with larger example data (not necessarily at all the same as below). Modify the data generation parameters in order to figure out which d in d-ary heap vs ordinary binary heap would be the most appropriate/fastest.

EX7. Bonus (1p) For which data the Kamp (CACM) paper implementation of the heap would actually outcompete all the above examples from EX6.

Let's use this example data generator for heaps:

import urllib.request; 
import random 

url = 'https://oeis.org/A192066/b192066.txt'

txt = urllib.request.urlopen(url).read().decode()
x = txt.split('\n')
xy = [ el.split() for el in x ]

# print(xy)
priority = dict()

random.seed(4)

for el in xy[ 3 : 40 ] :
  nr , key = int(el[0]) , int( el[1] )

  key = key % 30     # limit keys - note that heap can not grow if not enough possible keys 
  r = random.randint(8 ,20)

  priority[ key ] = priority.get( key , r ) - random.randint(1,5)

  if priority[ key ] < 1 or random.random() < 0.1 :
    print("deletemin" ) 
    priority[ key ] = 10 
    continue

  print( key, priority[ key ] )

  # if key is in heap but priority has decreased, decrease key 

This produces the sequence:

1 8
6 10
4 8
8 11
1 5
10 9
6 7
12 9
deletemin
14 14
8 9
deletemin
deletemin
18 7
10 4
20 9
6 5
deletemin
12 6
24 6
deletemin
26 7
14 10
28 8
8 8
0 17
24 1
2 7
deletemin
18 6
deletemin
18 7
deletemin
8 7
20 5
26 3
6 2