Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps, Maximum key deletion, Heapsort, Bottom-up heap construction , Top…
Heaps
Heaps properties
There exists exactly one essentially complete binary tree with n nodes. Its height is equal to floor of log2 n.
-
-
A heap can be implemented as an array by recording its elements in the topdown, 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 putting there a sentinel whose value is greater than every element in the heap. In such a representation:
the parental node keys will be in the first floor of n/2 positions of the array, while the leaf keys will occupy the last ceil of n/2 positions;
the children of a key in the array’s parental position i (1 ≤ i ≤ floor of n/2) will be in positions 2i and 2i + 1, and, correspondingly, he parent of a key in position i (2 ≤ i ≤ n) will be in position floor of i/2.
Heap is a clever, partially ordered data structure that is especially suitable for implementing
priority queues.
priority queue is a 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
-
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 (or simply complete), i.e., all its levels are full except The shape property—the binary tree is essentially complete (or simply complete), i.e., all its levels are full except
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.)
Key values in a heap are ordered top down; i.e., a sequence of values on any path from the root to a leaf is decreasing (nonincreasing, if equal keys are
allowed).
However, there is no left-to-right order in key values; i.e., there is no relationship among key values for nodes either on the same level of the tree or, more generally, in the left and right subtrees of the same node.
Maximum key deletion
-
-
The efficiency of deletion is determined by the number of key comparisons needed to “heapify” the tree after the swap has been made and the size of the tree is decreased by 1. Since this cannot require more key comparisons than twice the
heap’s height, the time efficiency of deletion is in O(log n) as well.
Heapsort
-
Since we already know that the heap construction stage of the algorithm is in
O(n), we have to investigate just the time efficiency of the second stage.
-
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 last, the resulting array will be exactly the original array sorted in increasing order.
-
-