Differences

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

--- courses:cs211:winter2018:journals:thetfordt:chapter2 [2018/01/28 19:12] – thetfordt
+++ courses:cs211:winter2018:journals:thetfordt:chapter2 [2018/01/29 20:32] (current) – thetfordt
@@ Line 38: / Line 38: @@
 The author then walks through the problem: that we want to be able to add, delete, and select elements quickly when an algorithm calls for it. The author then walks through exactly what a priority queue is and shows that, by using one, a linear sequence of priority queue operations can be used to sort n numbers.
-We then dive into heaps, as a data structure used to implement heaps, which turns out to be extraordinarily similar to a binary search tree represented as an array. The author then walks through the heap operations, such as adding, deleting, and the respective algorithms necessary to implement these operations: Heapify-Down and Heapify-Up. We covered both of these in class, and after reading the section, I feel that I have a very strong understanding the logic and runtime of each of them. The author then concludes the section by walking through the five primary operations surrounding heaps implementing priority queues: StartHeap, Insert, FindMin, Delete, and ExtractMin, citing the runtimes for each using the details from earlier in the section.
+We then dive into heaps, as a data structure used to implement priority queues, which turns out to be extraordinarily similar to a binary search tree represented as an array. The author then walks through the heap operations, such as adding, deleting, and the respective algorithms necessary to implement these operations: Heapify-Down and Heapify-Up.
+The Heapify-Up algorithm runs in O(log n) time. This algorithm adds an element to the end of a heap, determines if the element needs to be switched with its parent and if so, executes this swap and uses a recursive call.
+The Heapify-Down algorithm also runs in O(log n) time. This algorithm is used to delete an element from a heap while also maintaining the structure of the heap. It deletes the element at a position i, and then promptly places the element at the end of the heap in the deleted position. It then takes this new swapped element, determines which of its children (if it has children) is lower, and swaps with that child. After this, it just executes a recursive call, ultimately resulting in a deleted element and a proper heap structure.
+We covered both of these in class, and after reading the section, I feel that I have a very strong understanding the logic and runtime of each of them. The author then concludes the section by walking through the five primary operations surrounding heaps implementing priority queues: StartHeap, Insert, FindMin, Delete, and ExtractMin, citing the runtimes for each using the details from earlier in the section.
 I would rate the readability of this section at 9/10. It flowed nicely and was a nice refresher from what we covered in class.