Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps - Coggle Diagram
Heaps
Heap is a 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
-deleting an item with the highest priority
-adding a new item to the multiset
Notion of 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 (or simply complete). So, 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).
-
-
-
-
Heapsort
Definition
Heap sort is a comparison-based sorting technique based on Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.
-
Complexity
-
-
The temporal efficiency of Heapsort is the same class of Mergesort, and the Heapsort even have a better space efficiency than Mergesort. In general, the Heapsort has a worse temporal efficiency than Quicksort. Finding the k largest elements is in O(n+k log n).