CS2040s: Lab 2

Binary Heap Recap/ Binomial Heap

The top will always be the minimum or the maximum depending if it is a min heap or max heap

MakeHeap (1)

Insert (logn)

Minimum (1)

ExtractMax(logn) // Swap wif last index, extract

Extractmin (logn)

Union (n)

Decrease - key (logn)

Delete (logn)

Each Child is the parent /2

Binomial Heap is a collection of binomial trees where each binomial tree has a unique rank.

Each tree can only be in powers of 2. If there's two of the same rank, we combine it.

There cannot be the same rank together.

Extractmin -> logn

Findmin -> logn