Heap as array: Difference between revisions

Latest revision as of 23:12, 19 June 2015

General information

Abstract Data Structure: Bounded priority queue

Implementation Invariant:

For each object of "Heap as array", there is
1. a specific maximum number of items $N_{max} \in N$ , which is constant throughout the object's lifetime.
2. a current number of items $N \in N_{0}$ , which is dynamically changing, but it is $N \leq N_{max}$ at any time.
There is an internal type heap item with two components:
1. a component named $k e y$ of type $K$
2. a component named $I D$ , which is a natural number and ranges from $1, . . ., N_{max}$ .
There is an array $T h e H e a p$ with index range $1, . . ., N_{max}$ and component type heap item. The currently stored items are $T h e H e a p [1], . . ., T h e H e a p [N]$ .
There is an index handler $I H$ with maximum size $N_{max}$ and value type ${1, \dots, N_{max}}$ . For each used index $i \in {1, . . ., N_{max}}$ , the associated value is the position of one of the $N$ heap items in $T h e H e a p$ . As long as this heap item is stored, $i$ 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 $i$ is one-to-one.
Heap property: For each $i \in {2, . . ., N}$ , it is $T h e H e a p [i] . k e y \geq T h e H e a p [⌊ i / 2 ⌋] . k e y .$ .

The heap property may be viewed as follows: Imagine a binary tree of $N$ 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 ${1, . . ., N}$ :

The root is indexed $1$ .
For a node with $i$ , the left child (if existing) has index $2 * i$ , and the right child (if existing) has index $2 * i + 1$ .

Now associate the node with index $i$ with the key $T h e H e a p [i] . k e y$ . 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

@@ Line 1: / Line 1: @@
+[[Category:Videos]]
+{{#ev:youtube|https://www.youtube.com/watch?v=j-r4YOPFp7E|500|right||frame}}
 [[Category:Data Structures]]
 ==General information==
@@ Line 11: / Line 13: @@
 ## a component named <math>ID</math>, which is a [[Numbers#natural numbers|natural number]] and ranges from <math>1,...,N_\text{max}</math>.
 # There is an array <math>TheHeap</math> with index range <math>1,...,N_\text{max}</math> and component type heap item. The '''currently stored items''' are <math>TheHeap[1],...,TheHeap[N]</math>.
-# There is an array <math>Positions</math> with index range <math>1,...,N_\text{max}</math> and integral components from <math>\{1,...,N_\text{max}\}</math>.
+# 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 [[ordered sequence]] <math>Unused</math> of [[Numbers#natural numbers|natural numbers]], which has length <math>N_\text{max}-N</math> and stores pairwise different numbers from <math>\{1,...,N_\text{max}\}</math>.
-# For each <math>i\in\{1,...,N_\text{max}\}</math> not in <math>Unused</math>:
-## <math>Positions[i]</math> 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.
-## <math>TheHeap[Positions[i]].ID=i</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 [[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>.
 # For a node with <math>i</math>, the left child (if existing) has index <math>2*i</math>, and the right child (if existing) has index <math>2*i+1</math>.

Heap as array: Difference between revisions

Latest revision as of 23:12, 19 June 2015

General information

Remark

References

Navigation menu

Search