Scribd Logo
Upload

Welcome to Scribd!

  • 4 views

    Part 9 heap

    Uploaded by

    egyptian gamer

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    Part 9 heap

    Uploaded by

    egyptian gamer
    4 views15 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    4 views15 pages

    Part 9 heap

    Uploaded by

    egyptian gamer

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 15

    Data Structures and Algorithms

    Part 9: Heaps

    1 Data Structures and Algorithms Part 9


    Outline
    • Heaps
    • Introduction to Heaps
    • Heap implementation as an array
    • Inserting a node in a heap
    • Removing the maximum node
    • Expanding the Heap Array
    • Efficiency of heap operations
    • Building the heap with O(n)
    • Heap sort
    • Priority queue implementation using a heap

    2 Data Structures and Algorithms Part 9


    Introduction to Heaps
     A heap is a binary tree with these characteristics:
     It’s complete. This means it’s completely filled in, reading from left to
    right across each row, although the last row need not be full.
     It’s (usually) implemented as an array.
     the heap can be either a max heap in which the root has the
    max value or min heap in which the root has the min value
     Each node in a heap satisfies the heap condition.
     Any sorted array is a heap:
     Ascending order: min heap
     Descending order: max heap

    3 Data Structures and Algorithms Part 9


    4 Data Structures and Algorithms Part 9
    Heap implementation as an array
    The fact that a heap is
    a complete binary tree
    implies that there are
    no “holes” in the array
    used to represent it.
    Every cell is filled, from
    0 to N-1.
     If a node’s index
    number is index, this
    node’s left child is
    2*index + 1
     its right child is
    2*index + 2
     and its parent is
    (index-1) / 2

    5 Data Structures and Algorithms Part 9


    Inserting a node

    We didn’t build the heap using a tree its an array

    82 70 51 63 55 37 10 43 27 30 34 95

    82 70 51 63 55 95 10 43 27 30 34 37

    82 70 95 63 55 51 10 43 27 30 34 37

    95 70 82 63 55 51 10 43 27 30 34 37

    6 Data Structures and Algorithms Part 9


    Removing the maximum node

    95 82 51 63 70 37 10 43 27 55 34 30
    30 82 51 63 70 37 10 43 27 55 34
    82 30 51 63 70 37 10 43 27 55 34
    82 70 51 63 30 37 10 43 27 55 34
    82 70 51 63 55 37 10 43 27 30 34
    7 Data Structures and Algorithms Part 9
    Efficiency of Heap Operations
     For a heap with a substantial number of items, the trickle-up and trickle-down
    algorithms are the most time-consuming part of the operations we’ve seen.
    These algorithms spend time in a loop, repeatedly moving nodes up or down
    along a path.
     The trickleUp() method has only one major operation in its loop: comparing
    the key of the new node with the node at the current location.
     The trickleDown() method needs two comparisons: one to find the largest
    child and a second to compare this child with the “last” node.
     They must both copy a node from top to bottom or bottom to top to
    complete the operation.

    8 Data Structures and Algorithms Part 9


    Efficiency of Heap Operations(conts.)
     The trickleUp() and trickleDown() routines cycle through their loops L-1
    times, so the first takes time proportional to log N, and the second
    somewhat more because of the extra comparison.
     Thus, the heap operations we’ve talked about here all operate in O(log
    N) time.
     Heapify a single node takes O(Log N) time complexity where N is the
    total number of Nodes. Therefore, building the entire Heap will take N
    heapify operations and the total time complexity will be O(N*logN).
     In reality, building a heap takes O(n) time depending on the
    implementation.

    9 Data Structures and Algorithms Part 9


    Heapsort
     The efficiency of the heap data structure lends itself to a surprisingly simple and very
    efficient sorting algorithm called heapsort.
     The basic idea is to insert all the unordered items into a heap using the normal
    insert() routine. Repeated application of the remove() routine will then remove the
    items in sorted order. Here’s how that might look
     for(j=0; j<size; j++)
    theHeap.insert( anArray[j] ); // from unsorted array
    for(j=0; j<size; j++)
    anArray[j] = theHeap.remove(); // to sorted array
     Because insert() and remove() operate in O(logN) time, and each must be applied N
    times, the entire sort requires O(N*logN) time, which is the same as quicksort.
     However, it’s not quite as fast as quicksort, partly because there are more operations
    in the inner while loop in trickleDown() than in the inner loop in quicksort.
    10 Data Structures and Algorithms Part 9
    Priority queue implementation using a heap
     A priority queue is an Abstract Data Type (ADT) offering methods that allow removal
    of the item with the maximum (or minimum) key value, and insertion.
     As with other ADTs, priority queues can be implemented using a variety of
    underlying structures. In Chapter 4 we saw a priority queue implemented as an
    ordered array.
     The trouble with that approach is that, even though removal of the largest item is
    accomplished in fast O(1) time, insertion requires slow O(N) time.
     Another structure that can be used to implement a priority queue: the heap. A heap
    is a kind of tree. It offers both insertion and deletion in O(logN) time.
     Thus, it’s not quite as fast for deletion, but much faster for insertion. It’s the method
    of choice for implementing priority queues where speed is important and there will
    be many insertions.

    11 Data Structures and Algorithms Part 9


    Building a heap with O(n)
    1- the leaf nodes need not to be heapified as they already follow the heap
    property.
    2- The array representation of the complete binary tree contains the level order
    traversal of the tree.
     Modified algorithm:
     find the position of the last non-leaf node and perform the heapify operation of each
    non-leaf node in reverse level order.

    12 Data Structures and Algorithms Part 9


    Example : taking an array
    A= [6,8,10,9,11,18,15,14,13,20,22] build a max heap
     The array contain 11 elements
     Search for the first non-leaf element (10/2 -1).
    i.e element with index 4----- A[4]=11
    Heapify A[4]=11
    1. Find left child index 4*2+1=9
    2. Find right child index 4*2+2=10
    3. Compare A[4] with A[9] and A[10] and swap it with the biggest child (swap 11 with 22)
    4. The array becomes A=[6,8,10,9,22,18,15,14,13,20,11]
    Heapify A[3]=9
    Compare 9 with 14 and 13 and swap it with 14
    A=[6,8,10,14,22,18,15,13,9,20,11]

    13 Data Structures and Algorithms Part 9


    A=[6,8,10,14,22,18,15,13,9,20,11]
    Heapify A[2]=10
    Compare 10 with 18,15 ---swap 10 with 18
    A=[6,8,18,14,22,10,15,9,13,20,11]
    Heapify A[1]=8
    Compare 8 with 14 and 22 --- swap 8 and 22
    A=[6,22,18,14,8,10,15,9,13,20,11]
    Compare 8 with 20 and 11 ---- swap 8 with 20
    A=[6,22,18,14,20,10,15,9,13,8,11]
    Heapify A[0]=6
    Compare 6 with 22 and 18 ----- swap 6 and 22
    A=[22,6,18,14,20,10,15,9,13,8,11]
    Compare 6 with 14 and 20 ----- swap 6 with 20
    A=[22,20,18,14,6,10,15,9,13,8,11]
    Compare 6 with 8 and 11 ---- swap 6 with 11
    A=[22,20,18,14,11,10,15,9,13,8,6]
    14 Data Structures and Algorithms Part 9
    A=[22,20,18,14,11,10,15,9,13,8,6]

    22

    20 18

    14 11 10 15

    9 13 8 6

    15 Data Structures and Algorithms Part 9

    You might also like