Homework $4$

Problem $1.$ Binary heap

$($a$)$ Show the result of inserting $10,12,1,14,6,5,8,15,3,9,7,4,11,13,$ and $2,$ one at a time, into an initially empty binary heap.

$($b$)$ Show the result of using the linear$-$time algorithm to build a binary heap using the same input.

$($c$)$ Show the result of performing three deleteMin operations in the heap of the previous exercise.

Problem $2.$ d$-$heap

If a $d-$heap is stored as an array, for an entry located in position $i,$ where are the parents and children?

Problem $3.$ Leftist heap

$($a$)$ Show the result of inserting keys $1$ to $15$ in order into an initially empty leftist heap.

$($b$)$ Merge the two leftist heaps in Figure $1.$

Problem $4.$ Skew heap

$($a$)$ Merge the two skew heaps in Figure $1.$

$($b$)$ Show the result of inserting keys $1$ to $15$ in order into a skew heap.

Problem $5.$ Binomial queue

$($a$)$ Merge the two binomial queues in Figure $2.$

$($b$)$ Prove that a binomial tree of height $k$ has $([k],[d])$ nodes at depth $d.$

Figure $2$: Binomial queues