Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps and Heapsort, Bottom-up heap construction: It initializes the…
Heaps and Heapsort
Heap
It 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
-
Definition: 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 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.)5
There exists exactly one essentially complete binary tree with n nodes. Its height is equal to log2 n
-
Bottom-up heap construction: It initializes the essentially complete binary tree with n
nodes by placing keys in the order given and then “heapifies” the tree as follows
Top-down heap construction: The alternative (and less efficient) algorithm constructs a heap by successive
insertions of a new key into a previously constructed heap
-
-