Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps and Heapsort, There exists exactly one essentially complete binary…
Heaps and Heapsort
Heap is a clever, paetially oredered data structure that is especially suitable for implementing priority queues.
Priority queue is a multiset of items with an orderable chaacteristi called an item's priority, with the following operations: - Finding an item with the highest priority. - Deleting an item with the highest priority. - Adding a new item to the multiset.
Priority queues arise naturally in such applications as scheduling job executions by computer operating systems and traffic management by communication networks.
Notion of the Heap
A heap can be defined as a 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, all its levels are full except possibly the last level, where only some rightmost leaves may be missing.
-
- The parental dominance or heap property: The key in each node is greater than or equal to the keys in its children. (this condition is considered automatically satisfied for all leaves)
The key values in a heap are ordered top down. However, there is no left-to-right order in key values.
-
We could also define a heap as an array H[1..n] in which every element in position i in the first half of the array is greater than or equal to the elements in positions 2i and 2i + 1.
-
Heapsort
-
-
As a result, the array elements are eliminated in decreasing order. But since under the array implementation of heaps an element being deleted is placed lasr, the resulting array will be exactly the original array sorted in increasing order.
-
- There exists exactly one essentially complete binary tree with n nodes. Its height is equal to Log2n.
-
- The root of a heap always contains its largest element.
-
- A node of a heap considered with all its descendants is also a heap.
-