Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:shermanc:chapter2 [2018/01/30 02:42] – shermanc | courses:cs211:winter2018:journals:shermanc:chapter2 [2018/01/30 02:49] (current) – shermanc |
|---|
| ====== Chapter 2: Basics of Algorithm Analysis ====== | ====== Chapter 2: Basics of Algorithm Analysis ====== |
| | |
| | This chapter will attempt to serve as an introduction on understanding the resources required for run times and space usage of different algorithms and how they compare to one another. This will involve discussion of basic algorithms while progressing into more complicated and useful algorithms that require the use of sophisticated data structures. |
| |
| |
| In a heap, we have a tree where the lowest keys are at the top (index 1) and every key below is greater than or equal to the key above (index = 2i for left child and 2i + 1 for right child). This makes it perfect to use with a priority queue, as the highest priorities will be at the beginning of the heap and we won't need to iterate through the entire thing to find them. | In a heap, we have a tree where the lowest keys are at the top (index 1) and every key below is greater than or equal to the key above (index = 2i for left child and 2i + 1 for right child). This makes it perfect to use with a priority queue, as the highest priorities will be at the beginning of the heap and we won't need to iterate through the entire thing to find them. |
| |
| The procedure described to add elements to a heap is called "Heapify-up." In this, we will insert an element into the correct position, checking and making sure that the keys above are less than our inserted key and that the ones below are greater. We will divide our input by 2 (i // 2) to find the parent and then check if the input is smaller than its parent. If so, we will swap them and recursively run the algorithm. If not, then it will stay. We start Heapify-up by adding the element after the last current element in our heap. This corrects the heap in O(logi) time. | The procedure described to add elements to a heap is called "Heapify-up." In this, we will insert an element into the correct position, checking and making sure that the keys above are less than our inserted key and that the ones below are greater. We will divide our input by 2 (i / / 2) to find the parent and then check if the input is smaller than its parent. If so, we will swap them and recursively run the algorithm. If not, then it will stay. We start Heapify-up by adding the element after the last current element in our heap. This corrects the heap in O(logi) time. |
| |
| If we delete an element in a heap, the hold must be filled. If the element that we move into the hole is too small, we can use Heapify-up to fix this. But, if it is too large, we must use a new procedure, called "Heapify-down," to fix the problem. Heapify-down will check to see if 2i (input i) is greater than the length of the heap and if so will terminate. Otherwise it will check the children of i and swap our current position with the smaller child and then continue to recursively run until it is in the correct position. This will run in O(logn). | If we delete an element in a heap, the hold must be filled. If the element that we move into the hole is too small, we can use Heapify-up to fix this. But, if it is too large, we must use a new procedure, called "Heapify-down," to fix the problem. Heapify-down will check to see if 2i (input i) is greater than the length of the heap and if so will terminate. Otherwise it will check the children of i and swap our current position with the smaller child and then continue to recursively run until it is in the correct position. This will run in O(logn). |
| |
| This section as a whole seemed more of a review, as I felt as if I had a pretty good grasp on it after we covered it in class. I like the priority queue and its usage with heaps, as they are quite efficient and seemingly simple to implement and navigate, serving their respective purposes well. I would give this chapter an 8/10 as it was mainly review but was quite thorough in its explanations. | This section as a whole seemed more of a review, as I felt as if I had a pretty good grasp on it after we covered it in class. I like the priority queue and its usage with heaps, as they are quite efficient and seemingly simple to implement and navigate, serving their respective purposes well. I would give this chapter an 8/10 as it was mainly review but was quite thorough in its explanations. |
