CMPSC 24 Lecture Notes - Lecture 13: Priority Queue, Greatest And Least Elements, Binary Tree
Document Summary
0-relative storage index i parent: (i-1)/2 left child: 2i+1 right child: 2i+2. 1-relative location 0 not used index i parent: i/2 left child: 2i right child: 2i+1. The point: (cid:455)ou do(cid:374)"t (cid:374)eed a li(cid:374)k stru(cid:272)ture for (cid:272)o(cid:373)plete (cid:271)i(cid:374)ar(cid:455) tree, (cid:455)ou (cid:272)a(cid:374) do e(cid:448)er(cid:455)thi(cid:374)g (cid:449)ith an array. Basic operation insert(element) element = deletemin (or deletemax) No find operation somertimes also increasekey(element, amount) decreasekey(element, amount) Underlying structure used to implement priority queue heap adt deletemin --> minheap deletemax --> maxheap. I(cid:373)ple(cid:373)e(cid:374)ti(cid:374)g (cid:373)i(cid:374)heap for (cid:374)o(cid:449) . i(cid:374)(cid:448)ersel(cid:455) a(cid:374)alogous for (cid:373)a(cid:454)heap. Order: for each node in the minheap, the node is minimum element of its children (cid:894)(cid:272)hildre(cid:374) are greater + left a(cid:374)d right does(cid:374)"t ha(cid:448)e spe(cid:272)ial relatio(cid:374)ship(cid:895) Maxheap, node is max element of its children (children are smaller) Smallest element in minheap = root greatest element in maxheap = root. Insert(v) to minheap add(v) to the next empty position (shape property) Percolate v to the root to maintain order property if v > parent(v)
