Binary Heap

Question 1

What is a binary heap

Answer 1

an array representation of a heap ordered complete binary tree

Question 2

what is a property of heap order

Answer 2

every node key must be greater than than it’s child node

Question 3

what number do the indices start at in binary heap representation

Answer 3

at 1

Question 4

where is the largest key in a binary heap

Answer 4

root

pos 1

Question 5

how to insert into a binary heap

Answer 5

add node at end

swim it up

Question 6

how to remove maximum from a binary heap

Answer 6

exchange root(max) with node at the end
sink new root down to its correct positio

Question 7

cost of insertion into a heap

Answer 7

at most 1+logN compares

Question 8

cost of deleting max in binary heap

Answer 8

logN

Question 9

cost of finding max in binary heap

Answer 9

1

is the first element

Question 10

best case of insertion and deletion is when…

Answer 10

no sinking is needed

Question 11

why is binary heap more efficient than using arrays

Answer 11

splits searching time

array = N compares at most
binary heap = log N compares at most = holy grail

Question 12

how is heap sort implemented

Answer 12

build max heap using bottom up method

Question 13

worst case run time of heap sort

Answer 13

N log N

Question 14

what does it mean for an algorithm to be stable

Answer 14

preserves the order of duplicate keys

Question 15

what does it mean for an algorithm to be in place

Answer 15

does not need new memory allocated

Question 16

is mergesort an in place sorting algorithm

Answer 16

no, linear extra space is neede

Question 17

is quicksort an in place sorting algorithm

Answer 17

yes

Question 18

is quicksort a stable sorting algorithm

Answer 18

no

Question 19

is merge sort a stable algorithm

Answer 19

yes

Question 20

heap sort algorithm run time guarantee (average)

Answer 20

N log N

Question 21

heap sort algorithm best case run time

Answer 21

N