\documentclass[12pt]{article}

\input{cps130.tex}

\begin{document}

\title{Heaps (8)}
\author{Michael L. Littman}
\date{September 29th, 1998}

\maketitle 

\section{ANNOUNCEMENTS}

\ni First exam is a week from today.

\ni I'll try to have a sample exam available by tomorrow.  The form
will be 10 questions, each with four parts.  You will choose 5 of
these to do for credit (20 points each).  Additional parts of
questions can be attempted at no cost to you at $1/4$ full value.
Parts (a) and (b) of each will be worth 4 points each, and (c) and (d)
6 points each.  Each problem will be organized around an algorithm or
idea.

\ni Some potential function inequalities backwards in notes.

\section{DYNAMIC PROBLEMS}

\subsection{Dynamic Problems}

\ni The applications we've talked about so far have the basic form:
input, output, thank you computer.

\ni Many applications have a different flavor: computer maintains some
data in a data structure, various operations are performed on the
data:

\ul
\li adding new information,
\li removing outdated information,
\li querying the current set of data.
\el

\ni Examples: elevator simulation, customer lists.

\subsection{Elevator Simulation}

\ni We are trying to design an algorithm to control a bank of 10
elevators in a 100-floor office building.  At any moment in time, each
elevator is on some floor (or between floors), and contains some
number of passengers with some set of buttons pushed.

\ni The elevators need to make a decision each time a button is
pressed and/or an elevator stops and opens its doors.

\ni The simulator needs to keep track of all this and correctly
simulate all events in their proper order.

\ni This is a kind of {\em discrete event simulator\/}.

\subsection{Dynamic Operations}

\ni Some operations our elevator-simulator data structure needs to
support:

\ul

\li schedule an event for a time in the future,
\li find next event, 
\li remove current event,
\li merge two simulations together.

\el

\ni And these will need to happen fast because there will be a lot of
events (button pushes and elevator arrivals) over the course of the
simulation.

\subsection{Customer Lists}

\ni Earlier, we discussed sorting as an important operation in
telephone-book publishing.  This application is kind of special in
that the telephone book is only published once or twice a year, so all
the work can be done right before the publishing date.

\ni Consider, on the other hand, the database kept by
\href{http://www.americanexpress.com/cards/}{American Express} for
tracking ``cardmembers.'' This needs to be much more dynamic.

\ni Each customer has a record: name, customer id number, address,
perhaps some billing information (!).

\subsection{Dynamic Operations}

\ni We need to be able to quickly:

\ul

\li add new customers to the database,
\li look up a customer's record by name,
\li delete a customer,
\li list all customers sorted by name,
\li list all customers in a range of names,
\li add a group of customers,
\li split an entire group of infinitives (oops).
\el

\subsection{Ordered Trees}

\ni It turns out that binary trees are a wonderful way to flexibly
store dynamic information.

\ni Here's a tree $T$.  Some terminology:

\ul

\li root: top of the tree
\li node: some place in the tree
\li key: the value stored in a node
\li left child, right child: the nodes immediately beneath a node
\li subtree: tree rooted at some node
\li parent: the node immediately above a node
\li leaf: childless node
\li depth: distance from node to root (depth of a tree is the depth of
the deepest leaf)
\li height: distance to furthest leaf (height of a tree is the height
of the root)
\el

\ni What do we know about the height and depth of a tree?

\subsection{Representing Trees}

\ni There are a few ways to represent a tree $T$ with $n$ nodes.

\ni One particularly flexible way is in terms of three arrays.  For $0
\le i \le n-1$:

\ul

\li $T_v[i]$: The key for node $i$.
\li $T_p[i]$: The index of the parent of node $i$ ($-1$ for root).
\li $T_l[i]$: The index of the left child of node $i$ ($-1$ if there is none).
\li $T_r[i]$: The index of the right child of node $i$ ($-1$ if there is none).

\el

\ni How can we test if node $i$ is a leaf?


\section{HEAPS}

\subsection{Priority Queue}

\ni Rule \#3 of Good Algorithm Design: Keep complex information
organized in a good data structure.

\ni A data structure that supports insert and delete-min is called a
``priority queue.''

\subsection{Priority Queue for Elevator}

\ni These are the core operations we need for the elevator-simulator
application.  In the elevator simulator:

\ul

\li The records are events.
\li The keys are the time at which those events will occur.
\li We always want to execute the event with the ``smallest time''
(closest to the present).
\li Executing an event may result in other future events (elevator
arriving at lobby and picking up passengers results in elevator
planning to arrive at 5th floor at time $t+20$ seconds).

\el

\ni One nice implementation of a priority queue is the {\em heap\/}.


\subsection{Heap Definition}

\ni Complete $n$-node binary tree.

\ni All nodes (other than root) satisfy the ``heap property'':
$$T_v[i] \ge T_v[T_p[i]].$$

% \ni Example: 1, 3, 7, 9, 10, 9, 14, 15, 13, 16.

\ni \epsfig{file=figs07/heap.ps,width=4in}

\subsection{Some Properties of Heaps}

\ni Height is $\Theta(\log(n))$.

\ni Smallest item easy to identify.

\ni Where's the largest item?  Second smallest?  Third smallest?

%  (CLR Exercise 7.1-4)

\ni Like a bunch of sorted lists knitted together.

\ni How many nodes have one child?  Just a left child?  Just a right
child?


\subsection{Representing a Heap}

\ni Can use the multiple-array representation.

\ni Because binary tree is ``complete'' (packed to the left), there is
an easier way.

\ni Read off the keys by depth, left to right.

\ni Where are the two children of a node $i$?  How about the parent of
$i$?

\ni How recognize leaf?  Parent?

\subsection{Maintaining the Heap Property}

\ni A heap is a dynamic data structure, so we're going to have to
contend with changes.

\ni The most important changes can be handled by two basic operations:

\ul

\li Up-heapify: The entire heap is valid, except for item $i$, which
may violate the heap property by being smaller than its parent.

\li Down-heapify: The entire heap is valid, except for the root, which
might be too big.  (Who violates the heap property, then?)

\el

\ni These don't change the shape of the tree, just which records are
at which nodes.

\subsection{Down-Heapify}

\begin{verbatim}
void Down_Heapify( vector<int> & data, unsigned int i )
{
  unsigned int left = left_child( i );
  unsigned int right = right_child( i );
  bool hasleft = left < data.size();
  bool hasright = right < data.size();

  // data[i] is a leaf
  if( !hasleft && !hasright )
    return;

  // heap property is satisfied
  // left child is greater than parent and right child is greater than
  // parent if it exists
  if( hasleft && data[i] <= data[ left ]
      && ( ( hasright && data[i] <= data[ right ] )
	   || !hasright ) )
    return;

  // Otherwise, swap data[i] and the smaller of its children.
  unsigned int smaller;
  if( hasright && data[ right ] <= data[ left ] ) 
    smaller = right;
  else
    smaller = left;

  swap( data, i, smaller );
  
  // Start again on the child that changed (i.e., move data[i] down).
  Down_Heapify( data, smaller );
}
\end{verbatim}

\ni Look at node $i$ (initially the root).

\ul

\li If $\mbox{key}[i] \le \mbox{key}[\mbox{left}[i]]$ and
$\mbox{key}[i] \le \mbox{key}[\mbox{right}[i]]$, all is well.  (Why?)

\li Similarly if $i$ is a leaf.  (Why?)

\li Otherwise, swap $i$ and the smaller of its children.

\li Start again on the child that changed (i.e., move $i$ down).

\el

\ni We know that the only node that may violate the heap property is a
child of the new $i$.  (Why?)

\ni Kind of like bubblesort or insertion sort in a tree.  The root
value trickles down until it stops.

\ni Running Time?  (Maximum number of comparisons and swaps.)


\subsection{Up-Heapify}

% ML: code?

\ni A bit simpler.

\ni Look at node $i$ (initially $i=n$).

\ul

\li If $\mbox{key}[i] \ge \mbox{key}[\mbox{parent}[i]]$, all is well.  (Why?)

\li Similarly if $i$ is the root.  (Why?)

\li Otherwise, swap $i$ and its parent.

\li Start again on the parent that changed (i.e., move $i$ up).

\el

\ni We know that the only node that may violate the heap property is
the new $i$.  (Why?)

\ni Kind of like bubblesort or insertion sort in a tree.  The last
leaf value trickles up until it stops.

\ni Running Time?  (Maximum number of comparisons and swaps.)

\ni 


\subsection{Building a Heap from a List}

\ni Let $A$ be an $n$ element list.  We will turn $A$ into a heap (in
place).

\begin{verbatim}
void Build_Heap( vector<int> & data, unsigned int i )
{
  if( i >= data.size() )
    return;

  Build_Heap( data, left_child( i ) );
  Build_Heap( data, right_child( i ) );
  Down_Heapify( data, i );
}
\end{verbatim}

\ni Recall that {\tt leftchild(i)} is $2i$ and {\tt rightchild(i)} is
$2i+1$.

\ni Also, {\tt Down\_Heapify(A, i)} performs the down-heapify action
starting at node $i$.

\ni Correctness argument?  What does down-heapify do?

\subsection{Build-Heap Analysis}

\ni How would you analyze this?  What is the running time?

\ni Simple analysis and tighter analysis.


\subsection{Extract Min}

\ni Now that we can create a heap, how can we remove things from it?

\ni Clearly the minimum element is at the top.

\ni Now the number of elements in the heap has decreased by one.

\ni Which node should we move to the root?

\ni How do we restore the heap property?

\ni Running Time?

\subsection{Insert}

\ni Now we'll look at putting a new element into the heap.

\ni Where should it go?

\ni How do we restore the heap property?

\ni Running time?

\ni We can use insert repeatedly to build a heap from a set of $n$
elements.  What recurrence do we get for the running time?  How does
the running time of this compare to that of build-heap?

\subsection{Heap Sort}

\ni We can use heaps to sort.

\begin{verbatim}
void heapsort( vector<int> & data )
{
  unsigned int N = data.size()-1;	// Can't use zero slot.

  Build_Heap( data , 1 );

  for( unsigned int i = 0; i < N; i++ )
    data[N-i+1] = Extract_Min( data );

}
\end{verbatim}

\ni Running Time?  How is this nicer than merge sort?  Quicksort?

\epsfig{file=figs08/qsort.ps,height=3.5in}

\section{LISTING LARGEST ELEMENTS}

\ni Let's think about solving the following problem.  A web search
engine matches queries against all the documents in a database and
computes a score for each.  It then needs to present the best
documents to the user, in order.

\ul
\li[Step 0]: Formalize problem.
\li[Step 1]: Propose algorithms.
\li[Step 2]: Prove correctness.
\li[Step 3]: Prove running-time bounds.
\el


\end{document}

