Differences

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

--- courses:cs211:winter2018:journals:beckg:ch2 [2018/01/30 00:37] – [2.4: Survey of Common Running Times] beckg
+++ courses:cs211:winter2018:journals:beckg:ch2 [2018/01/30 04:48] (current) – beckg
@@ Line 104: / Line 104: @@
 This was a good section, 9/10. Definitely interesting and explains everything quite well.
+===== 2.5: More Complex Data Structure: Priority Queues =====
+As we know, a priority queue (PQ) is one that maintains a set of elements, each of which has an associated numeric value, or key. The smaller this key, the higher the priority. These support insertion and deletion and selection of element with smallest key. As is shown in the book, a sequence of //O(n)// priority queue operations can be used to sort a list of //n// numbers. So, if we can get each PQ operation to work in //O(log n)// time, then we will have an implementation of sorting in //O(n log n)// time.
+This PQ implementation takes the form of a //heap//. A heap is a binary tree whose keys are in //heap order//, meaning that the values of each node's children are greater than or equal to the parent node's value. An easy implementation of this is an array, where we call the first index 1 (which is the root of the heap), and then define for each parent node //i//, its left child is at //2i// and its right child at //2i + 1//.
+To implement the heap operations, we define ''Heapify-up'' and ''Heapify-down''. The former operates for a given node by checking if its parent's value is greater than its own, and if so, swapping the two. This is then repeated recursively until the condition is met or the value makes its way to the heap root. Heapify-down work's similarly, just by checking if the given node's value is greater than either of its children's values, and if so, swapping with the "smaller" of the children. Then this is done recursively down. Both of these guarantee the heap order and balance is kept upon insertion and deletion in //O(log n)// time due to a particular bit of cleverness: we only add or delete from the very last spot in the array. Then, to keep it balanced, say, for deletion of an arbitrary spot on the left side of the heap, we simply swap that deleted value with the value in the last spot, delete the one that was to be deleted, and then let the one from the end that we swapped into its location Heapify-up/down to its rightful place.
+=== Implementing PQs with Heaps ===
+Initializing the PQ array runs at most //O(N)//, where //N// is a constraint on the input size by being the size of the array. Due to the above Heapify operations, we can then insert and delete any element in //O(log n)// time. Finding the minimum value then takes //O(1)// time because it is simply the root of the heap--always the first element in our array. Thus, extracting the minimum value simply means removing that minimum value, therefore takes //O(log n)// time.
+So, as mentioned in our goal, we have found an implementation of the PQ for which each operation is //O(log n)//. So, we can then use this to implement a sort in //O(n log n)// time.
+This was a good section which complemented class very well. They seemed to get a little more caught in notation which led to some confusion at times, but still a 8/10 in my book.