Please enable JavaScript.

Coggle requires JavaScript to display documents.

M9 (Heap, Heapsort) - Coggle Diagram

- - - - Initialize the complete binary tree with n nodes by placing keys in the order given, then heapify the tree as follows:
        
        Starting with the last parental node, the algorithm checks whether this node satisfies the heap property. If it does not, exchange the node's key K with the larger key of its children and check again. This proccess continues until this node satisfies the heap property.
        
        After completing the heapification of the subtree of the current parental node, the algorithm proceeds to do this for the node's immediate predecessor. The algorithm stops after this is done for the root of the tree.
        
        Efficiency: 2n
    - - This algorithm works by successively inserting new keys into a previously constructed heap.
        
        First, insert a new node with key K in it after the last leaf of the existing heap. Then, sift K up to its appropriate place in the new heap as follows:
        
        Compare K with its parent's key; if the latter is greater than or equal to K, stop: the structure is a heap. Otherwise, swap these two keys and compare K with its new parent. This swapping continues until K is not greater than its last parent, or reaches the root.
        
        Efficiency: O(log n)
  - - - Multiset of Items with an orderable characteristic, called priority
      - These arise in several important algorithms, such as Dijkstra's
      - Operations
        
        Deleting an item with the highest priority
        
        Algorithm for Maximum Key Deletion from a heap:
        
        Exchange the root's key with the last K key of the heap
        
        Decrease the heap's size by 1
        
        Heapify the new, smaller tree by sifting K down the tree with the method depicted in the bottom-up heap construction algorithm.
        
        1 more item...
        
        Adding a new item to the multiset
        
        Finding an item with the highest priority
- - - - Thus, the array elements are eliminated in decreasing order. In the array implementation of heaps, however, an element being deleted is placed last. So the resulting array will be exactly the original array sorted in increasing order.
        
        Efficiency: O(n log n)
        
        Heap construction stage: O(n)
        
        Maximum deletions stage: O(n log n)
        
        Experiments show heapsort to be slower than quicksort but competes with mergesort.