### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# Data Structures and Algorithms CS 361L

UNM

GPA 3.76

### View Full Document

## 29

## 0

## Popular in Course

## Popular in ComputerScienence

This 8 page Class Notes was uploaded by Trent Dare on Wednesday September 23, 2015. The Class Notes belongs to CS 361L at University of New Mexico taught by Staff in Fall. Since its upload, it has received 29 views. For similar materials see /class/212205/cs-361l-university-of-new-mexico in ComputerScienence at University of New Mexico.

## Reviews for Data Structures and Algorithms

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/23/15

39 Build MaX Heap CS 361 Lecture 9 Build MaX Heap A Jared Saia University of New Mexico 1 heap size A length A 2 for LlengthA2ji gt 0i 7 7 a do Max Heapify Ai 39 Outline Example A42167911538 0 0 0 0 0 0 oobgjeob For NASA space is still a high priority Dan Quayle 6 G e Q Q o o Heap Sort a Priority Queues o Quicksort o o o o o p 90 gtob o 900 O 9 0 9 0 1 b b 39 MaX Heaplfy 39 Heap Sort ReVIew Max Heapify A i Heap Sort A l l Lefti 2 R ht 3 T 9 Q 1 Build MaX Heap A urges Z 4 4 2 for Ien th A 1 if 4 if l g heap sizeA and AU gt Am then largest 1 g Z gt Z a do exchange A1 and AI 5 If r S heap sizeA and AV gt Alargest then largest r 4 b heap size A heap size A 1 6 If largest 2 then C Max Hea if A l a exchange Ai and Aargest p y 39 b Max Heapify A largest 39 Example 39 AnalySIs o Heap Sort takes Onog n time Q What is best case run tirne7 Q What is runtirne if the array is already in sorted order7 a Q Correctness 39 Analysis We can prove correctness by using the following loop invariant 39 At the start of each iteration of the for loop the subarray A1i is a max heap containing the 2 smallest elements of A1n and the subarray Ai1n contains the n i largest elements of A1n in sorted order Priority Queues A Priority Queue is an ADT for a set S which supports the following operations Insert SX inserts as into the set S Maximum 5 returns the maximum element in S Extract Max S removes and returns the element of S with the largest key Increase Key SXk increases the value of x39s key to the new value k k is assumed to be as large as x39s current key note can also have an analagous min priority queue 39 Applications of Priority Queue Application Scheduling jobs on a workstation Priority Queue holds jobs to be performed and their priorities When a job is finished or interrupted highest priority job is chosen using Extract Max New jobs can be added using Insert note an application of a min priority queue is scheduling events in a simulation 39 o A Priority Queue can be implemented using heaps Implementation 10 o We39ll show how to implement each of these four functions using heaps ll 39 Heap MaXImum Heap Maximum A 39 Heap Extract Max 1 return A1 Heap Extract Max A 3 9 1Jgt 3 if heap size Alt1 then return error max Al A1 Aheap size A heap size A77 Max Heapify A1 return max 12 13 39 Hea p Increase Key Heap Increase Key A i key 1 if key lt Ai then error new key is smaller than current key 2 AU 2 key 3 while igt1 and AParent i lt Ai a do exchange AU and AParent i b i 2 Parent i 14 39 Example 0 o o b o o b Q 0 Q Q 0 0 0 0 0 0 0 b b 15 Heap Insert In Class Exercise l l 0 Imagine you have a min heap with the following operations defined and taking Olog n keydata Heap EXtract Min A Heap Insert A key 1 heap size A Heap Insert Allteydata 2 Aheap size A infinity 0 Now assume you39re given k sorted lists each of length nk 3 Heap Increase Key Aheap size A key 0 Use this min heap to give a Onlog k algorithm for merging these k lists into one sorted list of size n 16 18 l l Anal sis In Class Exercise 39 y 39 Hea Magtltimum takes 0 1 time Heap Extract Max takesolo 0 Q1 What is the high level idea for solving this problem p gn 0 Q2 What is the pseudocode for solving the problem Heap Increase Key takes 0009 n 0 Q339 What is the runtime analysis Hea Insert takes 0 lo 39 p gn 0 Q4 What would be an appropriate loop invariant for proving correctness of the algorithm Correctness 17 19 39 QUIcksort 39 The Algorithm PRE A is the array to be sorted pgt1 r is lt the size of A Based on divide and conquer strategy Worst case is 012 o PUST Ap r is in sorted order 0 0 Expected running time is 9nlog n O O Quicksort Apr if pltr q Partition Apr Quicksort Apq1 An In place sorting algorithm Almost always the fastest sorting algorithm Quicksort Aq1 r 20 22 l l uicksort Partition 39 Q 39 PRE Apr is the array to be partitioned pgt1 and r lt size of A Ar is the pivot element PUST Let A be the array A after the function is run 39Ihen A pr contains the same elements as Apr Further all elements in A pres 1 are lt Ar A res Ar 0 Divide Pick some element Aq of the array A and partition N and all Elements in A res1 r are gt Ar 39 Partition Apr A into two arrays A1 and A2 such that every element In A1 M J is g Aq and every element in A2 is gt Ap i 1 p s o Conquer Recursiver sort Aland A2 39 for jpjltr1j 0 Combine A1 concatenated With Aq concatenated With A2 if Ajltx is now the sorted version of A 1H exchange Ai and Aj exchange Ai1 and Ar return i1 21 23 l 39 Correctness of Partition Example 39 Consider the array 2 6 4 1 5 3 Basic idea The array is partitioned into four regions X is the pivot a Region 1 Region that is less than or equal to X a Region 2 Region that is greater than X a Region 3 Unprocessed region a Region 4 Region that contains X only Region 1 and 2 are growing and Region 3 is shrinking 24 Correctness 39 Loop Invariant Basic idea The array is partitioned into four regions X is the pivot 39 Region 1 Region that is less than or equal to X At the beginning of each iteration of the for loop for any indeX between p and 2 k a Region 2 Region that is greater than X between 1 and 7 1 a Re ion 3392Jn rocesied r ion 139 fps k 3i then AW S x g 39 p g 2Ifi1 kgj71thenAkgtx between 3 and r7 1 3 If k then AW a Region 4 Region that contains X only 39 T x r Region 1 and 2 are growing and Region 3 is shrinking 25 27 l 39 Todo 0 Finish Chapter 6 a Start Chapter 7 28

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I made $350 in just two days after posting my first study guide."

#### "Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.