[go: up one dir, main page]
Scribd
Upload
97 views29 pages

Ecs 36C Data Structures: Spring 2024 - Instructor Siena Saltzen

Uploaded by

jaya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
97 views29 pages

Ecs 36C Data Structures: Spring 2024 - Instructor Siena Saltzen

Uploaded by

jaya
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 29

ECS 36C

Data Structures
Spring 2024 - Instructor Siena Saltzen
Review Time

What’s covered on the midterm? Week 1 - 3


Some C++/Classes
Alg Analysis
ADT (Abstract Data Types) and OOP (Object Oriented Programming)
LDS (Linear Data Structure): Stacks, Queues, LL
Sorting
Searching
Heaps Part 1
Midterm Info
● I am allowing one 3x5 note card on the midterm
● 55 min
● In Person on Thurs
● Please bring a Laptop (and some scratch paper), otherwise paper tests will be
provided
● NO notes, AI, or outside resources
● Only given credit if taken in class
● 45 Questions -
○ Mostly Multiple choice
○ Few fill In
○ Three mid Programing
○ Two Hard Programming (One Bonus)
ReHeap
If the node we’re looking at is 28, then k = 4
The left child is 41 at index = 8
The right child is 52 at index = 9
The parent is 14 at index = 2
The more formal algorithms for insertion in and deletion from a heap
are in your textbook. You should make sure you understand the details.
Is that all there is?
We've explored some sorting algorithms in depth:
All these sorting algorithms will turn this…

this into this (some faster than others).


What next? - Issue #1

So we have the ability to sort with O(n lg n) speed, and search with O(lg n) speed.
That’s really good. But we still have some issues. What might those be?

Where are we gonna put that 7 billion element "world phone book" list in memory?
Finding that much contiguous available memory might be problematic. A data
structure that was more flexible, more dynamic, and much less dependent on
contiguous memory could be helpful. What kind of structure might that be?

Some sort of linked list structure seems like a possibility.


Issue #2

Now that we’ve sorted our 7 billion element list in O(n lg n) time, what
do we do if we want to add one more element in the right place? How
about if we add that element to the end of the existing list and then
apply quicksort to the whole thing again?

What input causes quicksort to perform with its absolute worst time
complexity (i.e. O(n^2))*?

* (Again, it depends on how you choose the pivots.)


Issue #2

So if we’re doing 1 billion comparisons per second, we can quicksort the original
unsorted list in less than 4 minutes, according to what we have learned. But once
the list is sorted, if we want to add an element that belongs just before the current
last item in the list, that’ll take more than 1500 years?!

Isn’t it nice that you know something about algorithm analysis now? Let’s try
another approach...
Issue #2

How about we just insert the element in its appropriate place by searching the
sorted array until we find the right place, then make a space by moving all the
elements past that place one space toward the back, like one pass of insertion
sort. What’s the time complexity of insertion now? Using binary search, we
can find the insertion point in O(lg n) comparisons, but moving elements will
take O(n) movements. O(n) beats O(n^2), but...
Maybe we could speed up the insertion time even more. Before we
hinted at a linked list structure for flexibility. Can we do binary search
on a singly-linked list to get that O(lg n) time complexity?

No, we have to be able to jump in both directions in the sequence to


make binary search work…
A doubly-linked list lets us move in both directions. So binary search
should be possible, but we can’t move the pointers (left, right, mid)
with simple index arithmetic. We would have to do link traversals, and
as long as we’re traversing the links in the list, we might as well look at
the values at the nodes as we pass by, and this just turns into linear
search. What is the linked structure that makes it all come together?
But first...
Let's look at one more search technique …

Recently, we’ve seen linear search – O(n)...


...and we’ve seen binary search – O(lg n)...
The latter gives better time complexity, but it requires sorted data.
And both are effectively “trial and error” approaches to solving the search problem.
Wouldn’t it be nice if we could get even better performance, without the dependency
on sorting?
Heapsort
We can use a heap as the foundation for a very efficient sorting algorithm called
heapsort.

Heapsort consists of two phases:


Heapify: build a heap using the elements to be sorted
Sort: Use the heap to sort the data

This can all be done in place in the array that holds the heap, but it’s easier to see if
we draw the trees instead of the array. Once you see how it works with trees, make
sure you understand how it works in place in the array.
Heapsort

Here’s the heapify component:

for each item in the sequence to be sorted


add the item to the next available position in the complete binary tree
restore the heap property (using ReheapUp)

Say we want to sort the sequence 5 2 1 4 3:


Heapsort - heapify

Say we want to sort the sequence 5 2 1 4 3:

The sequence is heapified


Heapsort - Sort

Now for the sorting:

while the heap is not empty


● remove the first item from the heap by
swapping it with the last item in the
heap
● reduce the size of the heap by one
● restore the heap property

Now it’s sorted, but it’s largest to smallest (reading top to bottom, left to right). We
created a min heap, and we ended up with the sequence sorted from largest to
smallest. The same thing will happen when sorting in place in the array.
Heapsort

In the array-based heapsort example in the book (which you should


study), the original sequence was heapified into a max heap, and the
resulting sorted sequence in the array went from smallest to largest.
Just something to keep in mind.
Heapsort analysis
A heap of size n has lg n levels. Building a heap requires finding the correct location
for each item in a heap with lg n levels. Because there are n items to insert in the
heap and each insert is O(lg n), the time to heapify the original unsorted sequence
using ReheapUp or Sift-up is O(n lg n). During sorting, we have n items to remove
from the heap, which then is also O(n lg n). Because we can do it all in the original
array, no extra storage is required.
https://www.explainxkcd.co
m/wiki/index.php/1185:_Ine
ffective_Sorts

You might also like