Heap

Heap is a specialized tree-based data structure that satisfies the heap property:
Max heap:
>if B is a child node of A, then key(A) ≥ key(B). This implies that the element with the greatest key is always in the root node.
>binary tree should complete.It means every level in the tree till the end should b full,then the last row should b filled from left 2 right with no location leaving empty.
Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min heap.

Heap Sort

Heapsort is one of the best general-purpose sorting algorithms, a Comparison_sort1. and part of the selection sort family.

  • elements to be sorted are inserted into a heap,
  • the heap organizes the elements added to it in such a way that either the largest value (in a max-heap) or the smallest value (in a min-heap) can be quickly extracted.
  • Moreover, because this operation preserves the heap's structure, the largest/smallest value can be repeatedly extracted until none remain. This gives us the elements in order.

In doing so, the only extra space required is that needed to store the heap. In order to achieve constant space overhead, we use a trick: we store a binary heap (or alternatively, a heap with more than two children) inside the part of the input array which has not yet been sorted. (The structure of this heap is described at Binary heap: Heap implementation.) Heapsort makes use of two standard heap operations: insertion and root deletion. Each time we delete (extract) the maximum, we place it in the last location of the array not yet occupied, and use the remaining prefix of the array as a heap holding the remaining unsorted elements:

Heap of remaining unsorted elements Sorted elements
  • Somewhat slower in practice on most machines than a good implementation of quicksort(in general)
    • worst-case O(n log n) runtime.(advantage)
  • Heapsort is an in-place algorithm and is not a stable sort.

Time Complexity

Example : Trie

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.