These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else

Download 186.06 Kb.
Size186.06 Kb.
1   ...   16   17   18   19   20   21   22   23   24


    • Run-time (adjacency list)?
      • Algo. looks at each edge in the graph, just as BFS does
        • However, now for each edge, a PQ operation will be done
          • Insert a vertex, edge pair
          • Delete the vertex with the smallest edge
          • Update a vertex to give it a new (better) edge
        • If we implement the PQ in a smart way, we can do these operations very efficiently
          • Use a HEAP for the PQ itself, allowing Insert and Delete to be time Theta(lg v)
          • Have an additional indexing array to locate the vertices in the heap, enabling Update to also be time Theta(lg v)
        • Thus, assuming the graph is connected, the overall run-time is Theta(e(lg v)) for an adjacency list


    • What about an adjacency matrix?
      • We don't need a heap for the PQ in this case
      • Instead traverse the val[] array at each step to find the best edge
        • Since it takes Theta(v) to traverse the row of the matrix to find the neighbors of the current vertex, an extra V to find the best vertex to pick next does not add any extra asymptotic time
      • Thus, the overall run-time is the same as for BFS – Theta(v2)
    • How do they compare?
      • elgv vs v2
      • Depending upon how e relates to v, one may be preferable -- see notes from board

Shortest Path

  • Djikstra's Shortest Path algorithm
    • Can be implemented using the SAME PFS that we just discussed for MST
    • The only difference is the measure used for the priority
      • With MST, we wanted the smallest overall weight
        • For each vertex we wanted the smallest edge that could connect it to the tree
      • With SP, we want the smallest weight PATH from the starting vertex to each other vertex
    • See trace in handout and on board

Heap Implementation of PQ

  • We saw need for a PQ in adjacency list PFS
  • Let's look a bit closer at PQs
    • We need 3 primary operations
      • Insert an object into the PQ
      • Find the object with best priority
      • Remove the object with best priority
        • Often called DeleteMin or DeleteMax
    • How to implement?
      • 2 obvious implementations:
        • Unsorted Array
        • Sorted Array

Priority Queues

    • Unsorted Array PQ:
      • Insert:
      • FindMin:
      • DeleteMin:
  • Add new item at end of array: Theta(1) run-time
  • Search array for smallest: Theta(N) run-time
  • Search array for smallest and delete it: Theta(N) run-time
  • For a N inserts and deletes, total time is Theta(N2)

Priority Queues

    • Sorted Array PQ:
      • Insert:
      • FindMin:
      • DeleteMin:
  • Add new item in reverse sorted order: Theta(N) run-time
  • Smallest item at end of array: Theta(1) run-time
  • Delete item from end of array: Theta(1) run-time
  • For a N inserts and deletes, total time is Theta(N2)


  • How can we improve our overall run-time?
    • We could use a BST
      • This would give Theta(lgN) for each operation
        • Discuss
      • However, it is MORE than we need
        • It maintains a complete ordering of the data, but we only need a PARTIAL ORDERING of the data
    • Instead we will use a HEAP


    • Note that we don't care how T.lchild.val relates to T.rchild.val
      • But BST does care, which is why it gives a complete ordering
    • Ok, how do we do our operations:
      • FindMin is easy – ROOT of tree
      • Insert and DeleteMin are not as trivial
      • For both we are altering the tree, so we must ensure that the HEAP PROPERTY is reestablished


    • Idea of Insert:
      • Add new node at next available leaf
      • Push the node "up" the tree until it reaches its appropriate spot
        • We'll call this upHeap
      • See example on board
    • Idea of DeleteMin:
      • We must be careful since root may have two children
        • Similar problem exists when deleting from BST
      • Instead of deleting root node, we overwrite its value with that of the last leaf


      • Then we delete the last leaf -- easy to delete a leaf
      • But now root value may not be the min
      • Push the node "down" the tree until it reaches its appropriate spot
        • We'll call this downHeap
      • See example on board
    • Run-time?
      • Complete Binary Tree has height  lgN
      • upheap or downheap at most traverse height of the tree
      • Thus Insert and DeleteMin are always Theta(lgN) worst case
      • For N Inserts + DeleteMins total = Theta(NlgN)

Implementing a Heap

  • How to Implement a Heap?
    • We could use a linked binary tree, similar to that used for BST
      • Will work, but we have overhead associated with dynamic memory allocation and access
    • But note that we are maintaining a complete binary tree for our heap
    • It turns out that we can easily represent a complete binary tree using an array

Download 186.06 Kb.

Share with your friends:
1   ...   16   17   18   19   20   21   22   23   24

The database is protected by copyright © 2020
send message

    Main page