Please enable JavaScript.

Coggle requires JavaScript to display documents.

Heaps and heapsort - Coggle Diagram

- - - - There exists exactly one essentially complete binary tree with n nodes. Its
        height is equal to [log2 n]
      - A node of a heap considered with all its descendants is also a heap
      - The root always contains the heap's larget element
      - 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
      - Implementing a heap with array is much simpler and more efficient with arrays
        
        There are two principal
        alternatives to construct a heap for a given list of keys
        
        bottom up
        
        More efficient
        
        It initializes the essentially complete binary tree with n
        nodes by placing keys in the order given and then “heapifies” the tree
        
        Starting with the last parental node, the algorithm checks whether the parental dominance holds for the key in this node. If it does not, the algorithm exchanges
        the node’s key K with the larger key of its children and checks whether the parental dominance holds for K in its new position
        
        After completing the “heapification” of the
        subtree rooted at the current parental node, the algorithm proceeds to do the same for the node’s immediate predecessor. The algorithm stops after this is done for
        the root of the tree
        
        1 more item...
        
        top down
        
        constructs a heap by successive
        insertions of a new key into a previously constructed heap
        
        We do this by attaching a new node with key K in it after the last leaf of the
        existing heap. Then evaluate K up to its appropriate place in the new heap
        
        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 parents
        
        1 more item...
- - - - deleting an item with the highest priority
      - adding a new item to the multiset
      - finding an item with the highest priority
- - - - Heapsort’s time efficiency falls in the same class as that of mergesort. However, Timing experiments on random files show that heapsort runs more slowly than
        quicksort
- - - - Maximum Key Deletion from a heap
        
        Step 1 Exchange the root’s key with the last key K of the heap.
        
        Step 2 Decrease the heap’s size by 1.
        
        Step 3 “Heapify” the smaller tree by sifting K down the tree exactly in the same way we did it in the bottom-up heap construction algorithm. That is, verify the parental dominance for K: if it holds, we are done; if not, swap K with the larger of its children and repeat this operation until the parental dominance condition holds for K in its new position
        
        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