Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2014:journals:deirdre:chapter2 [2014/01/22 04:01] – [Section 2.5 - A More Complex Data Structure: Priority Queues] tobind
+++ courses:cs211:winter2014:journals:deirdre:chapter2 [2014/01/22 04:03] (current) – [Section 2.4 - A Survey of Common Running Times] tobind
@@ Line 79: / Line 79: @@
 There are cases where one encounters running times that are asymptotically smaller than linear. Since it takes linear time just to read the input, these situations tend to arise in a model of computation where the input can be "queried' indirectly rather than read completely and the goal is to minimize the amount of querying that must be done. Example, binary search algorithm -> running time of //O(log n)//.
+I give this section a 8.5.
 ====== Section 2.5 - A More Complex Data Structure: Priority Queues ======
 **The Problem**
@@ Line 127: / Line 125: @@
              Heapify-down(H,j)
          Endif
-Assume that //H// is an array and //w// is the element in postion //i//. We say that "H is almost a heap with the key of //H[i] too big", if there is a value α ≤ key(//w//) such that lowering the value of key(//w//) to α would make the resulting array satisfy the heap property.
+Assume that //H// is an array and //w// is the element in postion //i//. We say that "H is almost a heap with the key of //H[i]// too big", if there is a value α ≤ key(//w//) such that lowering the value of key(//w//) to α would make the resulting array satisfy the heap property.
 - The procedure Heapifydown(//H,i//) fixes the heap property in //O//(log //n//) time, assuming that //H// is almost a heap with the key value of //H[i]// too big. Using Heapify-up or Heapify-down, we can delete a new element in a heap of //n// elements in //O//(log //n//) time.