ch 6 priority queues (heaps)

Question 1

binary heap

Answer 1

a binary tree that is completely filled with exception of the bottom level (complete binary tree)

Question 2

locating child/parent

Answer 2

left child = 2i
right child = 2i + 1
i/2 = parent

Question 3

heap order property

Answer 3

smallest element is the root

Question 4

insert (percolate up)

Answer 4

first, make a hole in the next avalailable spot
if x can be placed in the spot without violating heap order, place it there
otherwise, find parent, place it there, and place x in the hole that the parent created

element is percolated up until correct location

O(logn)

Question 5

deletemin (percolate down)

Answer 5

delete root
find the smallest of the children and insert into the hole
keep repeating

O(logn)

Question 6

buildHeap

Answer 6

all items are inserted into the tree
first exam the subtrees on the very bottom. Do necessary percolate ups if there is a leaf that is larger than the parent
keep doing this for each level of the tree