Please enable JavaScript.
Coggle requires JavaScript to display documents.
Mapa Mental 10 - Coggle Diagram
Mapa Mental 10
Priotrity Queue
multiset of items with an orderable
characteristic called an item’s priority, with the following operations:
Finding an item with the highest (i.e., largest) priority
-
-
Priority queues arise naturally in such ap-plications as scheduling job executions by computer operating systems and traffic management by communication networks.
-
-
-
-
Heaps
it's a clever, partially ordered data structure that is especially suitable for implementing priotrity queues.
binary tree with keys assigned to its
nodes, one key per node, provided the following two conditions are met:
The shape property—the binary tree is essentially complete (or simply complete), i.e., all its levels are full except possibly the last level, where only somerightmost leaves may be missing.
The parental dominance or heap property—the key in each node is greaterthan or equal to the keys in its children. (This condition is considered auto-matically satisfied for all leaves.)
Important topics
- There exists exactly one essentially complete binary tree with n nodes.
Its height is equal to log2 n.
- The root of a heap always contains its largest element.
- A node of a heap considered with all its descendants is also a heap.
- A heap can be implemented as an array by recording its elements in the top-down, left-to-right fashion. It is convenient to store the heap’s elements in positions 1 through n of such an array, leaving H[0] either unused or puttingthere a sentinel whose value is greater than every element in the heap. In sucha representation,
the parental node keys will be in the first n/2 positions of the array,
while the leaf keys will occupy the last n/2 positions;
the children of a key in the array’s parental position i (1 ≤ i ≤ n/2) willbe in positions 2i and 2i + 1, and, correspondingly, the parent of a key inposition i (2 ≤ i ≤ n) will be in position i/2.
Heapsort
-
-
As a result, the array elements are eliminated in decreasing order.