Adaptive Fibonacci and Pairing Heaps

Andrew Frohmader

(March 2020)

1 Introduction

In this brief note, we present two adaptive heaps. See [4] and [5] for discussion of adaptive heaps. The first structure is a modification of the Fibonacci heap [3]. The second, a relaxation of the Fibonacci like structure which is similar to a pairing heap [2]. While the specification of the data structures is complete, the analysis is not. We welcome interested parties to complete it.

2 Adaptive Fibonacci Heap

For ease of comparison, our structure mirrors that of CLRS Chapter 19 [1]. We include one additional pointer $root$ at the top level pointing to the first element added to the root list.

2.1 Operations

INSERT, FIND-MIN, UNION, and DECREASE-KEY are identical to CLRS 19 and have $O(1)$ amortized cost using the same potential function.

The entire difference is in how we build our trees during the EXTRACT-MIN operation. We add adaptivity to presorted input. We only need to modify the CONSOLIDATE $(H)$ operation of CLRS 19.2. For completeness, we include the EXTRACT-MIN code from 19.2. When we iterate over lists, we assume the iteration proceeds from the first element added to the list to the last element added to the list (oldest to newest).

Algorithm 1 EXTRACT-MIN

(H)

z=H.min

z\neq NIL

for each child

x

z

add

x

to the root list of

H

x.p=NIL

remove

z

from the root list of

H

z==z.right

H.min=NIL

else

H.min=z.right

CONSOLIDATE

(H)

H.n=H.n-1

return

z

Algorithm 2 CONSOLIDATE

(H)

Initialize a new array

A[0\dots D(H.n)]

with all elements

NIL

for each node

x

in the root list of

H

APPEND

(x,x.degree,A)

Create a new empty root list for

H

for each node

x

A

x.parent==NIL

insert

x

into

H

’s root list

x<H.min

H.min=x

Algorithm 3 APPEND

(x,d,A)

y=A[d]

y==NIL

break

else if

y<x

y.degree==d

Make

x

a child of

y

incrementing

y.degree

y.parent==NIL

APPEND

(y,y.degree,A)

else if

y.parent==NIL

Make

y

a child of

x

incrementing

x.degree

A[d]=x

2.2 Example

Say we insert the random sequence

11,13,6,10,1,8,14,12,9,5,4,3,7,2

into our heap and then call EXTRACT-MIN. EXTRACT-MIN removes $1$ and consolidates the remaining nodes. Note: the “else if $y.parent==NIL$ ” statement in APPEND causes $A[d]=x$ with $x.degree=d+1$ . These nodes are darkened in the example. The “if $y.degree==d$ ” statement ensures a darkened node is not given an additional child.

Refer to caption — Figure 1: Example of CONDSOLIDATE

Lemma 1.

Let $x$ be any node in the heap, and $k=x.degree$ . Let $y_{1},y_{2},\dots,y_{k}$ denote the children of $x$ in the order in which they were linked to $x$ , from earliest to latest. Then $y_{1}.degree\geq 0$ and $y_{i}.degree\geq i-2$ for $i=2,3,\dots,k$ .

Proof.

Clearly $y_{1}.degree\geq 0$ . For $i\geq 2$ , we note that when $y_{i}$ was linked to $x$ , all $y_{1},y_{2},\dots,y_{i-1}$ were children of $x$ , and so we must have had $x.degree\geq i-1$ . Let $x.degree=d$ . We first show that when linked, $y_{i}.degree\geq d\geq i-1$ . There are only two ways in which $y_{i}$ could have become a child of $x$ in CONSOLIDATE.

1.

If $x<y$ , $A[d]=x$ , and we call APPEND $(y,d,A)$ . Then $y.degree=d$ .
2.

If $x<y$ , $A[d]=y$ , $y.parent=NIL$ , and we call APPEND $(x,d,A)$ . Then $y.degree=d$ or $y.degree=d+1$ .

Thus, $y.degree\geq d\geq i-1$ . Since $y_{i}$ was linked, it has lost at most one child, since it would have been cut by CASCADING-CUT if it had lost two children. We conclude that $y_{i}.degree\geq i-2$ . ∎

With Lemma 1, the remaining propositions can be proved nearly identically to CLRS.

Corollary 1.1.

The maximum degree of all nodes is $O(\lg n)$ .

Theorem 2.

EXTRACT-MIN runs in $O(\lg n)$ amortized time.

Theorem 3.

DECREASE-KEY runs in $O(1)$ amortized time.

We would like to have some dynamic optimality result like this:

Conjecture 1.

The above heap is competitive with all comparison based heaps that have an $O(1)$ amortized decrease key.

3 Pairing Like Heap

3.1 Structure

Use the same structure as used above except we do not need to store degree information in each node.

Two nice things about this structure. One, it makes the locally optimal choice of only leaving local min in the root list. Two, starting from a list of degree 0 nodes, the degree of any node in the final tree is $O(\lg n)$ . Thus, it has better structural properties than the standard pairing heap.

3.2 Operations

Again, operations are the same as for Fibonacci heap presented in CLRS 19 except for the CONSOLIDATE procedure in EXTRACT-MIN. The CONSOLIDATE code uses pointers $p$ for previous, $c$ for current and travels in loops around the circularly linked root list until only one root remains. A $cycle$ of CONSOLIDATE is one loop from beginning to end of root list.

Algorithm 4 CONSOLIDATE

(H)

p=H.root

c=p.right

while

c\neq p

n=c.right

p<c

Make

c

a child of

p

and remove

c

from

root

list

else if

p.parent=None

Make

p

a child of

c

and remove

p

from

root

list

p=c

c=n

H.min=H.root=c

Lemma 4.

Let $l_{i}$ be the root list after the $i^{th}$ cycle of CONSOLIDATE. Then $l_{i+1}$ contains the local minimum of $l_{i}$ .

Lemma 5.

Let $k$ be the number of roots in $H$ ’s root list prior to CONSOLIDATE. The increase in degree of any node caused by CONSOLIDATE is less than $2\lg k$ .

Conjecture 2.

The degree of any node $x$ in $H$ is $O(\lg n)$ .

Conjecture 3.

DECREASE-KEY runs in $O(1)$ amortized time. EXTRACT-MIN runs in $O(\lg n)$ amortized time.

Conjecture 4.

Let $X$ be a sequence of $n$ numbers, $m_{1}$ be the subsequence of local minimums in $X$ in the order in which they appear in $X$ , and $m_{i}$ be the local minimums in $m_{i-1}$ in the order they appear in $m_{i-1}$ . Say $|m_{k}|=1$ and $|m_{k-1}|>1$ . Then a comparison sort is dynamically optimal if and only if it sorts every list in

\Theta(nk)

Again, something about optimality, although statement of this conjecture depends on Conjecture 3.

Conjecture 5.

The above heap is competitive with all comparison based heaps that have an $O(1)$ amortized decrease key.

3.3 Example

Say we insert the same random sequence

11,13,6,10,1,8,14,12,9,5,4,3,7,2

into this heap and then call EXTRACT-MIN. EXTRACT-MIN removes $1$ and consolidates the remaining nodes. The resulting structure is presented below.

References

[1] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
[2] Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1:111–129, 11 1986.
[3] Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596–615, July 1987.
[4] Andrew Frohmader. List heaps. CoRR, abs/1802.05662, 2018.
[5] László Kozma and Thatchaphol Saranurak. Smooth heaps and a dual view of self-adjusting data structures. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, page 801–814, New York, NY, USA, 2018. Association for Computing Machinery.

(a)	(b)
(c)	(d)
(e)	(f)
(g)	(h)

(i)	(j)
(k)	(l)
(m)	(n)