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



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

PFS

    • 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

PFS

    • 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)

Heaps

  • 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

Heaps

    • 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

Heaps

    • 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

Heaps

      • 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 ©sckool.org 2020
send message
    Main page
united states
main idea
other side
main points
vast majority
total number
following questions
last sentence
most important
supreme court
subject matter
different types
thesis statement
federal government
main point
middle east
soviet union
main ideas
topic sentence
same time
political economy
well-being
early years
writing process
final exam