Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2011:journals:chen:chapter_2 [2011/01/25 01:48] – [2.5 A More Complex Data Structure:Priority Queues] zhongc | courses:cs211:winter2011:journals:chen:chapter_2 [2011/01/25 01:52] (current) – [2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays] zhongc | ||
|---|---|---|---|
| Line 51: | Line 51: | ||
| Refer back to the 1/17 slide for the breakdown of the running time of O(N²) of the the total running time. | Refer back to the 1/17 slide for the breakdown of the running time of O(N²) of the the total running time. | ||
| + | |||
| + | |||
| + | Interesting/ | ||
| ===== 2.4 A Survey of Common Running Times ===== | ===== 2.4 A Survey of Common Running Times ===== | ||
| Line 84: | Line 87: | ||
| Note: Summary of running times. P20 slide 1/19 | Note: Summary of running times. P20 slide 1/19 | ||
| + | |||
| + | |||
| + | Interesting/ | ||
| ===== 2.5 A More Complex Data Structure: | ===== 2.5 A More Complex Data Structure: | ||
| Motivation: | Motivation: | ||
| Line 102: | Line 108: | ||
| Implementing data structures: for sorting | Implementing data structures: for sorting | ||
| If we use unsorted lists: N² -why? | If we use unsorted lists: N² -why? | ||
| + | |||
| If we use array: logn*N² | If we use array: logn*N² | ||
| + | |||
| If we use heaps: NlogN | If we use heaps: NlogN | ||
| Implementation of Heaps: | Implementation of Heaps: | ||
| + | Know the implementation of the **Heapify-up** and **Heapify-down** with an array based implementation. | ||
| + | |||
| + | Interesting/ | ||
