Heap as array: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
[[Category:Checkup]]
[[Category:Videos]]
{{#ev:youtube|https://www.youtube.com/watch?v=j-r4YOPFp7E|500|right||frame}}
[[Category:Data Structures]]
[[Category:Data Structures]]
==General information==
==General information==
Line 14: Line 15:
# There is an [[Index handler|index handler]] <math>IH</math> with maximum size <math>N_\text{max}</math> and value type <math>\{1,\ldots,N_\text{max}\}</math>. For each used index <math>i\in\{1,...,N_\text{max}\}</math>, the associated value is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.
# There is an [[Index handler|index handler]] <math>IH</math> with maximum size <math>N_\text{max}</math> and value type <math>\{1,\ldots,N_\text{max}\}</math>. For each used index <math>i\in\{1,...,N_\text{max}\}</math>, the associated value is the position of one of the <math>N</math> heap items in <math>TheHeap</math>. As long as this heap item is stored, <math>i</math> is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers <math>i</math> is one-to-one.
# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.
# '''Heap property:''' For each <math>i\in\{2,...,N\}</math>, it is <math>TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key.</math>.
In summary, <math>Positions</math> stores the positions of all heap items, <math>Unused</math> stores all currently unused indexes of <math>Positions</math>, and the ID of each heap item refers back to its corresponding index in <math>Positions</math>.
The heap property may be viewed as follows: Imagine a [[Directed Tree|binary tree]] of <math>N</math> nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from <math>\{ 1,...,N \}</math>:
The heap property may be viewed as follows: Imagine a [[Directed Tree|binary tree]] of <math>N</math> nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from <math>\{ 1,...,N \}</math>:
# The root is indexed <math>1</math>.
# The root is indexed <math>1</math>.

Latest revision as of 23:12, 19 June 2015

General information

Abstract Data Structure: Bounded priority queue

Implementation Invariant:

  1. For each object of "Heap as array", there is
    1. a specific maximum number of items [math]\displaystyle{ N_\text{max}\in\mathbb{N} }[/math], which is constant throughout the object's lifetime.
    2. a current number of items [math]\displaystyle{ N\in\mathbb{N}_{0} }[/math], which is dynamically changing, but it is [math]\displaystyle{ N\le N_\text{max} }[/math] at any time.
  2. There is an internal type heap item with two components:
    1. a component named [math]\displaystyle{ key }[/math] of type [math]\displaystyle{ \mathcal{K} }[/math]
    2. a component named [math]\displaystyle{ ID }[/math], which is a natural number and ranges from [math]\displaystyle{ 1,...,N_\text{max} }[/math].
  3. There is an array [math]\displaystyle{ TheHeap }[/math] with index range [math]\displaystyle{ 1,...,N_\text{max} }[/math] and component type heap item. The currently stored items are [math]\displaystyle{ TheHeap[1],...,TheHeap[N] }[/math].
  4. There is an index handler [math]\displaystyle{ IH }[/math] with maximum size [math]\displaystyle{ N_\text{max} }[/math] and value type [math]\displaystyle{ \{1,\ldots,N_\text{max}\} }[/math]. For each used index [math]\displaystyle{ i\in\{1,...,N_\text{max}\} }[/math], the associated value is the position of one of the [math]\displaystyle{ N }[/math] heap items in [math]\displaystyle{ TheHeap }[/math]. As long as this heap item is stored, [math]\displaystyle{ i }[/math] is permanently associated with this heap item (and can hence be used to locate and access this heap item at any time). The correspondence between the heap items and these numbers [math]\displaystyle{ i }[/math] is one-to-one.
  5. Heap property: For each [math]\displaystyle{ i\in\{2,...,N\} }[/math], it is [math]\displaystyle{ TheHeap[i].key\ge TheHeap[\lfloor i/2 \rfloor ].key. }[/math].

The heap property may be viewed as follows: Imagine a binary tree of [math]\displaystyle{ N }[/math] nodes such that each height level except for the last one is full, and the last one is filled from left to right. The nodes have pairwise different indexes from [math]\displaystyle{ \{ 1,...,N \} }[/math]:

  1. The root is indexed [math]\displaystyle{ 1 }[/math].
  2. For a node with [math]\displaystyle{ i }[/math], the left child (if existing) has index [math]\displaystyle{ 2*i }[/math], and the right child (if existing) has index [math]\displaystyle{ 2*i+1 }[/math].

Now associate the node with index [math]\displaystyle{ i }[/math] with the key [math]\displaystyle{ TheHeap[i].key }[/math]. Then the heap property says that the key of a node is not larger than the keys of its children. In this case, we say that i fulfills the heap property.

In particular, the minimum key is associated with the root.

Remark

The implementations of the methods Bounded priority queue: number and Bounded priority queue: find minimum are trivial and, hence, left out here.

References