Algoritmer och Datastrukturer
frslag till lsning 20.1 (simple on Hashtable),
21.1, 21.2, 21.3 (simple about the representation of priority queues with binary heaps.)
1. (20.1) 0..10
*
2. (21.1) A binary heap is a Complete Binary Tree (no missing nodes in the tree, the only level that might not be filled is the bottom level, which is filled from left to right) and for every node, the key is larger or equal than the parents key (also known as the heap property).
3. (21.2) For a the node placed at position i we find
* left child at 2i
* right child at 2i+1
* parent at i/2
4. (21.3) insert 10 12 1 14 6 5 8 15 3 9 7 4 11 13 2 We show the tree which is easier to visualize than its representation in an array!
10
10
/
12
10 ( ) 1
/ \ / \ / \
12 ( ) 12 10 12 10
1
/ \
12 10
/
14
1 1 1
/ \ / \ / \
12 10 ( ) 10 6 10
/ \ / \ / \
14 ( ) 14 12 14 12
1 1 1
/ \ / \ / \
6 10 6 ( ) 6 5
/ \ / / \ / / \ /
14 12 ( ) 14 12 10 14 12 10
and so on, the structural property and the heap property are maintained after every insert.