DS C4 Heaps

The time complexity is $O(N)$ when normal heaps merge, which just neglects the original heap structure and simply builds a new heap.

Leftist Heaps

Definitions

Null path length

The null path length, NPL of any node $X$: the length of the shortest path from $X$ to a node without two children.

Speacially, Define $Npl(NULL) = -1$.

$$Npl(X) = \min_{c \in children(X)}\{Npl(c) + 1\}$$

Leftist heap property

leftist heap property: For every node $X$ in the heap, the Npl of the left child is at least as large as that of the right child. i.e

$$\forall X \in Heap(H), Npl(X.Left) \ge Npl(X.Right)$$

Right Path

The right

It follows that the right path ought to be short. Indeed, the right path down a leftist heap is as short as any in the
heap. Otherwise, there would be a path that goes through some, node X and takes the left child. Then X would violate the leftist property.

Lemma 1

A leftist tree with $r$ nodes on the right path must have at least $2^r - 1$ nodes.

Skew Heaps

Binomial Queue

Structure Definition

A binomial queue is not a heap-ordered tree, but rather a collection of heap-ordered trees, known as a forest. Each heap-ordered tree is a binomial tree.

• A binomial tree of height 0 is a one-node tree.

• A binomial tree, $B_k$, of height $k$ is formed by attaching a binomial tree $B_{k – 1}$, to the root of another binomial tree $B_{k – 1}$ with smaller root element value .

Property

• $B_k$ consists of a root with $k$ children, which are $B_0,B_1\cdots,B_{k-1}$.
• $B_k$ has exactly $2^k$ nodes.
• The number of nodes at depth $d$ is $\left( \begin{array}{c} k \\ d \end{array}\right)$

Bk structure + heap order + one binomial tree for each height

​ A priority queue of any size can be uniquely represented by a

​ collection of binomial trees.

Operations

FindMin

Return the minimum key is in one of the roots.

There are at most roots, hence Tp = O( ).

Insert

Delete Min