Please enable JavaScript.

Coggle requires JavaScript to display documents.

M10 - Algorithms and Data Structures - Coggle Diagram

- - - - 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
        
        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
        
        Note that key values in a heap are ordered top down
      - important properties of heaps
        
        There exists exactly one essentially complete binary tree with n nodes. Its height is equal to floor(log2 n).
        
        The root of a heap always contains its largest element.
        
        A node of a heap considered with all its descendants is also a heap
        
        A heap can be implemented as an array by recording its elements in the top down, left-to-right fashion
        
        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
        
        their actual implementations are usually much
        simpler and more efficient with arrays.
      - How can we construct a heap for a given list of keys?
        
        The first is the bottom-up heap construction
        
        How efficient is this algorithm in the worst case?
        
        , a heap of size n can be constructed with
        fewer than 2n comparisons.
        
        The alternative (and less efficient): top-down heap construction
        
        the time efficiency of insertion is in O(log n)
        
        How can we delete an item from a heap?
        
        the time efficiency of deletion is in O(log n) as well
    - - This is a two-stage algorithm that works as follows.
        
        Stage 1 (heap construction): Construct a heap for a given array
        
        the heap construction stage of the algorithm is in O(n)
        
        For both stages,
        we get O(n) + O(n log n) = O(n log n)
        
        time efficiency of heapsort is, in fact, in Θ(n log n) in both the worst and average
        cases.
        
        Thus, heapsort’s time efficiency falls in the same class as that of mergesort.
        Unlike the latter, heapsort is in-place, i.e., it does not require any extra storage.
        
        Timing experiments on random files show that heapsort runs more slowly than quicksort but can be competitive with mergesort
        
        Stage 2 (maximum deletions): Apply the root-deletion operation n − 1 times to the remaining heap.
        
        C(n) ∈ O(n log n)
        
        As a result, the array elements are eliminated in decreasing order.
    - - Recall that a 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 multise
      - The heap is also the data structure that serves as a cornerstone of a theoretically important sorting algorithm called heapsort