Pairing Heap

This module proposes several implementations of the pairing heap data structure [FSST1986]. See the Wikipedia article Pairing_heap for more information on this min-heap data structure.

  • PairingHeap_of_n_integers: a pairing heap data structure with fixed capacity \(n\). Its items are integers in the range \([0, n-1]\). Values can be of any type equipped with a comparison method (<=).

  • PairingHeap_of_n_hashables: a pairing heap data structure with fixed capacity \(n\). Its items can be of any hashable type. Values can be of any type equipped with a comparison method (<=).

  • PairingHeap: interface to a pairing heap data structure written in C++. The advantages of this data structure are that: its capacity is unbounded; items can be of any hashable type equipped with a hashing method that can be supported by std::unordered_map; values can be of any specified type equipped with a comparison method (<=). This data structure is for internal use and therefore cannot be accessed from a shell.

EXAMPLES:

Pairing heap of \(n\) integers in the range \([0, n-1]\):

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(10); P
PairingHeap_of_n_integers: capacity 10, size 0
sage: P.push(1, 3)
sage: P.push(2, 2)
sage: P
PairingHeap_of_n_integers: capacity 10, size 2
sage: P.top()
(2, 2)
sage: P.decrease(1, 1)
sage: P.top()
(1, 1)
sage: P.pop()
sage: P.top()
(2, 2)

sage: P = PairingHeap_of_n_integers(10)
sage: P.push(1, (2, 'a'))
sage: P.push(2, (2, 'b'))
sage: P.top()
(1, (2, 'a'))

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(10)); P
PairingHeap_of_n_integers: capacity 10, size 0
>>> P.push(Integer(1), Integer(3))
>>> P.push(Integer(2), Integer(2))
>>> P
PairingHeap_of_n_integers: capacity 10, size 2
>>> P.top()
(2, 2)
>>> P.decrease(Integer(1), Integer(1))
>>> P.top()
(1, 1)
>>> P.pop()
>>> P.top()
(2, 2)

>>> P = PairingHeap_of_n_integers(Integer(10))
>>> P.push(Integer(1), (Integer(2), 'a'))
>>> P.push(Integer(2), (Integer(2), 'b'))
>>> P.top()
(1, (2, 'a'))

Pairing heap of \(n\) hashables:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(10); P
PairingHeap_of_n_hashables: capacity 10, size 0
sage: P.push(1, 3)
sage: P.push('b', 2)
sage: P.push((1, 'abc'), 4)
sage: P.top()
('b', 2)
sage: P.decrease((1, 'abc'), 1)
sage: P.top()
((1, 'abc'), 1)
sage: P.pop()
sage: P.top()
('b', 2)

sage: # needs sage.graphs
sage: P = PairingHeap_of_n_hashables(10)
sage: P.push(('a', 1), (2, 'b'))
sage: P.push(2, (2, 'a'))
sage: g = Graph(2, immutable=True)
sage: P.push(g, (3, 'z'))
sage: P.top()
(2, (2, 'a'))
sage: P.decrease(g, (1, 'z'))
sage: P.top()
(Graph on 2 vertices, (1, 'z'))
sage: while P:
....:     print(P.top())
....:     P.pop()
(Graph on 2 vertices, (1, 'z'))
(2, (2, 'a'))
(('a', 1), (2, 'b'))

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(10)); P
PairingHeap_of_n_hashables: capacity 10, size 0
>>> P.push(Integer(1), Integer(3))
>>> P.push('b', Integer(2))
>>> P.push((Integer(1), 'abc'), Integer(4))
>>> P.top()
('b', 2)
>>> P.decrease((Integer(1), 'abc'), Integer(1))
>>> P.top()
((1, 'abc'), 1)
>>> P.pop()
>>> P.top()
('b', 2)

>>> # needs sage.graphs
>>> P = PairingHeap_of_n_hashables(Integer(10))
>>> P.push(('a', Integer(1)), (Integer(2), 'b'))
>>> P.push(Integer(2), (Integer(2), 'a'))
>>> g = Graph(Integer(2), immutable=True)
>>> P.push(g, (Integer(3), 'z'))
>>> P.top()
(2, (2, 'a'))
>>> P.decrease(g, (Integer(1), 'z'))
>>> P.top()
(Graph on 2 vertices, (1, 'z'))
>>> while P:
...     print(P.top())
...     P.pop()
(Graph on 2 vertices, (1, 'z'))
(2, (2, 'a'))
(('a', 1), (2, 'b'))
class sage.data_structures.pairing_heap.PairingHeap_class[source]

Bases: object

Common class and methods for PairingHeap_of_n_integers and PairingHeap_of_n_hashables.

capacity()[source]

Return the maximum capacity of the heap.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.capacity()
5
sage: P.push(1, 2)
sage: P.capacity()
5

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.capacity()
5
>>> P.push(Integer(1), Integer(2))
>>> P.capacity()
5
empty()[source]

Check whether the heap is empty.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.empty()
True
sage: P.push(1, 2)
sage: P.empty()
False

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.empty()
True
>>> P.push(Integer(1), Integer(2))
>>> P.empty()
False
full()[source]

Check whether the heap is full.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(2)
sage: P.full()
False
sage: P.push(0, 2)
sage: P.push(1, 3)
sage: P.full()
True

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(2))
>>> P.full()
False
>>> P.push(Integer(0), Integer(2))
>>> P.push(Integer(1), Integer(3))
>>> P.full()
True
pop()[source]

Remove the top item from the heap.

If the heap is already empty, we do nothing.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5); P
PairingHeap_of_n_integers: capacity 5, size 0
sage: P.push(1, 2); P
PairingHeap_of_n_integers: capacity 5, size 1
sage: P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 0
sage: P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 0

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5)); P
PairingHeap_of_n_integers: capacity 5, size 0
>>> P.push(Integer(1), Integer(2)); P
PairingHeap_of_n_integers: capacity 5, size 1
>>> P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 0
>>> P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 0
size()[source]

Return the number of items in the heap.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.size()
0
sage: P.push(1, 2)
sage: P.size()
1

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.size()
0
>>> P.push(Integer(1), Integer(2))
>>> P.size()
1

One may also use Python’s __len__:

sage: len(P)
1

>>> from sage.all import *
>>> len(P)
1
top()[source]

Return the top pair (item, value) of the heap.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.push(1, 2)
sage: P.top()
(1, 2)
sage: P.push(3, 1)
sage: P.top()
(3, 1)

sage: P = PairingHeap_of_n_integers(3)
sage: P.top()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.push(Integer(1), Integer(2))
>>> P.top()
(1, 2)
>>> P.push(Integer(3), Integer(1))
>>> P.top()
(3, 1)

>>> P = PairingHeap_of_n_integers(Integer(3))
>>> P.top()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap
top_value()[source]

Return the value of the top item of the heap.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.push(1, 2)
sage: P.top()
(1, 2)
sage: P.top_value()
2

sage: P = PairingHeap_of_n_integers(3)
sage: P.top_value()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.push(Integer(1), Integer(2))
>>> P.top()
(1, 2)
>>> P.top_value()
2

>>> P = PairingHeap_of_n_integers(Integer(3))
>>> P.top_value()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap
class sage.data_structures.pairing_heap.PairingHeap_of_n_hashables[source]

Bases: PairingHeap_class

Pairing Heap for \(n\) hashable items.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(5); P
PairingHeap_of_n_hashables: capacity 5, size 0
sage: P.push(1, 3)
sage: P.push('abc', 2); P
PairingHeap_of_n_hashables: capacity 5, size 2
sage: P.top()
('abc', 2)
sage: P.decrease(1, 1)
sage: P.top()
(1, 1)
sage: P.pop()
sage: P.top()
('abc', 2)

sage: P = PairingHeap_of_n_hashables(5)
sage: P.push(1, (2, 3))
sage: P.push('a', (2, 2))
sage: P.push('b', (3, 3))
sage: P.push('c', (2, 1))
sage: P.top()
('c', (2, 1))
sage: P.push(Graph(2, immutable=True), (1, 7))
sage: P.top()
(Graph on 2 vertices, (1, 7))
sage: P.decrease('b', (1, 5))
sage: P.top()
('b', (1, 5))

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(5)); P
PairingHeap_of_n_hashables: capacity 5, size 0
>>> P.push(Integer(1), Integer(3))
>>> P.push('abc', Integer(2)); P
PairingHeap_of_n_hashables: capacity 5, size 2
>>> P.top()
('abc', 2)
>>> P.decrease(Integer(1), Integer(1))
>>> P.top()
(1, 1)
>>> P.pop()
>>> P.top()
('abc', 2)

>>> P = PairingHeap_of_n_hashables(Integer(5))
>>> P.push(Integer(1), (Integer(2), Integer(3)))
>>> P.push('a', (Integer(2), Integer(2)))
>>> P.push('b', (Integer(3), Integer(3)))
>>> P.push('c', (Integer(2), Integer(1)))
>>> P.top()
('c', (2, 1))
>>> P.push(Graph(Integer(2), immutable=True), (Integer(1), Integer(7)))
>>> P.top()
(Graph on 2 vertices, (1, 7))
>>> P.decrease('b', (Integer(1), Integer(5)))
>>> P.top()
('b', (1, 5))
contains(item)[source]

Check whether the specified item is in the heap.

INPUT:

  • item – the item to consider

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(5)
sage: 3 in P
False
sage: P.push(3, 33)
sage: 3 in P
True
sage: 100 in P
False

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(5))
>>> Integer(3) in P
False
>>> P.push(Integer(3), Integer(33))
>>> Integer(3) in P
True
>>> Integer(100) in P
False
decrease(item, new_value)[source]

Decrease the value of specified item.

This method is more permissive than it should as it can also be used to push an item in the heap.

INPUT:

  • item – the item to consider

  • new_value – the new value for item

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(5)
sage: 3 in P
False
sage: P.decrease(3, 33)
sage: 3 in P
True
sage: P.top()
(3, 33)
sage: P.push(1, 10)
sage: P.top()
(1, 10)
sage: P.decrease(3, 7)
sage: P.top()
(3, 7)

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(5))
>>> Integer(3) in P
False
>>> P.decrease(Integer(3), Integer(33))
>>> Integer(3) in P
True
>>> P.top()
(3, 33)
>>> P.push(Integer(1), Integer(10))
>>> P.top()
(1, 10)
>>> P.decrease(Integer(3), Integer(7))
>>> P.top()
(3, 7)
pop()[source]

Remove the top item from the heap.

If the heap is already empty, we do nothing.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(5); len(P)
0
sage: P.push(1, 2); len(P)
1
sage: P.push(2, 3); len(P)
2
sage: P.pop(); len(P)
1
sage: P.pop(); len(P)
0
sage: P.pop(); len(P)
0

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(5)); len(P)
0
>>> P.push(Integer(1), Integer(2)); len(P)
1
>>> P.push(Integer(2), Integer(3)); len(P)
2
>>> P.pop(); len(P)
1
>>> P.pop(); len(P)
0
>>> P.pop(); len(P)
0
push(item, value)[source]

Insert an item into the heap with specified value (priority).

INPUT:

  • item – a hashable object; the item to add

  • value – the value associated with item

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(5)
sage: P.push(1, 2)
sage: P.top()
(1, 2)
sage: P.push(3, 1)
sage: P.top()
(3, 1)

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(5))
>>> P.push(Integer(1), Integer(2))
>>> P.top()
(1, 2)
>>> P.push(Integer(3), Integer(1))
>>> P.top()
(3, 1)
top()[source]

Return the top pair (item, value) of the heap.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(5)
sage: P.push(1, 2)
sage: P.top()
(1, 2)
sage: P.push(3, 1)
sage: P.top()
(3, 1)

sage: P = PairingHeap_of_n_hashables(3)
sage: P.top()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(5))
>>> P.push(Integer(1), Integer(2))
>>> P.top()
(1, 2)
>>> P.push(Integer(3), Integer(1))
>>> P.top()
(3, 1)

>>> P = PairingHeap_of_n_hashables(Integer(3))
>>> P.top()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap
top_item()[source]

Return the top item of the heap.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(5)
sage: P.push(1, 2)
sage: P.top()
(1, 2)
sage: P.top_item()
1

sage: P = PairingHeap_of_n_hashables(3)
sage: P.top_item()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(5))
>>> P.push(Integer(1), Integer(2))
>>> P.top()
(1, 2)
>>> P.top_item()
1

>>> P = PairingHeap_of_n_hashables(Integer(3))
>>> P.top_item()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap
value(item)[source]

Return the value associated with the item.

INPUT:

  • item – the item to consider

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
sage: P = PairingHeap_of_n_hashables(5)
sage: P.push(3, 33)
sage: P.push(1, 10)
sage: P.value(3)
33
sage: P.value(7)
Traceback (most recent call last):
...
ValueError: 7 is not in the heap

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_hashables
>>> P = PairingHeap_of_n_hashables(Integer(5))
>>> P.push(Integer(3), Integer(33))
>>> P.push(Integer(1), Integer(10))
>>> P.value(Integer(3))
33
>>> P.value(Integer(7))
Traceback (most recent call last):
...
ValueError: 7 is not in the heap
class sage.data_structures.pairing_heap.PairingHeap_of_n_integers[source]

Bases: PairingHeap_class

Pairing Heap for items in range \([0, n - 1]\).

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5); P
PairingHeap_of_n_integers: capacity 5, size 0
sage: P.push(1, 3)
sage: P.push(2, 2)
sage: P
PairingHeap_of_n_integers: capacity 5, size 2
sage: P.top()
(2, 2)
sage: P.decrease(1, 1)
sage: P.top()
(1, 1)
sage: P.pop()
sage: P.top()
(2, 2)

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5)); P
PairingHeap_of_n_integers: capacity 5, size 0
>>> P.push(Integer(1), Integer(3))
>>> P.push(Integer(2), Integer(2))
>>> P
PairingHeap_of_n_integers: capacity 5, size 2
>>> P.top()
(2, 2)
>>> P.decrease(Integer(1), Integer(1))
>>> P.top()
(1, 1)
>>> P.pop()
>>> P.top()
(2, 2)
contains(item)[source]

Check whether the specified item is in the heap.

INPUT:

  • item – nonnegative integer; the item to consider

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: 3 in P
False
sage: P.push(3, 33)
sage: 3 in P
True
sage: 100 in P
False

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> Integer(3) in P
False
>>> P.push(Integer(3), Integer(33))
>>> Integer(3) in P
True
>>> Integer(100) in P
False
decrease(item, new_value)[source]

Decrease the value of specified item.

This method is more permissive than it should as it can also be used to push an item in the heap.

INPUT:

  • item – nonnegative integer; the item to consider

  • new_value – the new value for item

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: 3 in P
False
sage: P.decrease(3, 33)
sage: 3 in P
True
sage: P.top()
(3, 33)
sage: P.push(1, 10)
sage: P.top()
(1, 10)
sage: P.decrease(3, 7)
sage: P.top()
(3, 7)

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> Integer(3) in P
False
>>> P.decrease(Integer(3), Integer(33))
>>> Integer(3) in P
True
>>> P.top()
(3, 33)
>>> P.push(Integer(1), Integer(10))
>>> P.top()
(1, 10)
>>> P.decrease(Integer(3), Integer(7))
>>> P.top()
(3, 7)
pop()[source]

Remove the top item from the heap.

If the heap is already empty, we do nothing.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5); P
PairingHeap_of_n_integers: capacity 5, size 0
sage: P.push(1, 2); P
PairingHeap_of_n_integers: capacity 5, size 1
sage: P.push(2, 3); P
PairingHeap_of_n_integers: capacity 5, size 2
sage: P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 1
sage: P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 0
sage: P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 0

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5)); P
PairingHeap_of_n_integers: capacity 5, size 0
>>> P.push(Integer(1), Integer(2)); P
PairingHeap_of_n_integers: capacity 5, size 1
>>> P.push(Integer(2), Integer(3)); P
PairingHeap_of_n_integers: capacity 5, size 2
>>> P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 1
>>> P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 0
>>> P.pop(); P
PairingHeap_of_n_integers: capacity 5, size 0
push(item, value)[source]

Insert an item into the heap with specified value (priority).

INPUT:

  • item – nonnegative integer; the item to consider

  • value – the value associated with item

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.push(1, 2)
sage: P.top()
(1, 2)
sage: P.push(3, 1)
sage: P.top()
(3, 1)

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.push(Integer(1), Integer(2))
>>> P.top()
(1, 2)
>>> P.push(Integer(3), Integer(1))
>>> P.top()
(3, 1)
top()[source]

Return the top pair (item, value) of the heap.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.push(1, 2)
sage: P.top()
(1, 2)
sage: P.push(3, 1)
sage: P.top()
(3, 1)

sage: P = PairingHeap_of_n_integers(3)
sage: P.top()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.push(Integer(1), Integer(2))
>>> P.top()
(1, 2)
>>> P.push(Integer(3), Integer(1))
>>> P.top()
(3, 1)

>>> P = PairingHeap_of_n_integers(Integer(3))
>>> P.top()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap
top_item()[source]

Return the top item of the heap.

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.push(1, 2)
sage: P.top()
(1, 2)
sage: P.top_item()
1

sage: P = PairingHeap_of_n_integers(3)
sage: P.top_item()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.push(Integer(1), Integer(2))
>>> P.top()
(1, 2)
>>> P.top_item()
1

>>> P = PairingHeap_of_n_integers(Integer(3))
>>> P.top_item()
Traceback (most recent call last):
...
ValueError: trying to access the top of an empty heap
value(item)[source]

Return the value associated with the item.

INPUT:

  • item – nonnegative integer; the item to consider

EXAMPLES:

sage: from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
sage: P = PairingHeap_of_n_integers(5)
sage: P.push(3, 33)
sage: P.push(1, 10)
sage: P.value(3)
33
sage: P.value(7)
Traceback (most recent call last):
...
ValueError: 7 is not in the heap

>>> from sage.all import *
>>> from sage.data_structures.pairing_heap import PairingHeap_of_n_integers
>>> P = PairingHeap_of_n_integers(Integer(5))
>>> P.push(Integer(3), Integer(33))
>>> P.push(Integer(1), Integer(10))
>>> P.value(Integer(3))
33
>>> P.value(Integer(7))
Traceback (most recent call last):
...
ValueError: 7 is not in the heap