Floyd’s buildHeap, Sorting - University of Washington

CSE 373: Data Structures and Algorithms

Floyd's buildHeap, Sorting

Autumn 2018

Shrirang (Shri) Mare shri@cs.washington.edu

Thanks to Kasey Champion, Ben Jones, Adam Blank, Michael Lee, Evan McCarty, Robbie Weber, Whitaker Brand, Zora Fung, Stuart Reges, Justin Hsia, Ruth Anderson, and many others for sample slides and materials ...

Today

- Heap review and Array implementation of Heap - Floyd's buildHeap algorithm - Intro to Sorting - Insertion sort - Heap sort

!2

Heap review

Heap is a tree-based data structure that satisfies

- (a) structure property: it's a complete tree

- (b) heap property, which states:

- for min-heap: paren t ch ildren - for max-heap: paren t ch ildren

- Operations (for min-heap):

- removeMin()

- peekMin()

- insert()

- Applications: priority queue, sorting, ..

!3

removeMin()

1

54

3

94

62

39

11

96 95 75 82 43 50 36 49

min-heap

Calls: removeMin()

function removeMin last = last node in the tree minvalue = root swap root with last percolateDown(root) return minvalue

end function

AAADVnicbVLbbhMxEPUmlJZwS+GRF4ukUpFQlfSFviAqcREvSEWQtlISRV7vJLHqy8oeJ0SrfAGv8G/wM8BsLtCkjLTa43NmPBdPmmsVsNX6mVSqt3Zu7+7dqd29d//Bw/r+o/PgopfQkU47f5mKAFpZ6KBCDZe5B2FSDRfp1etSv5iAD8rZzzjLoW/EyKqhkgKJGtR/91IYKVsIPXJe4djMa9uMksS9i1aWEYUH4ybwQdl5QfQnFAi8qUXAJn/Jyz+3LgOuLMcxcPQAf72MshOhI5Cjdw6bayFMRc6bC4pPKePqvrWcg6c+Cb1xU3u49Hu2Fj1g9Pbf3RT11mbrams9sNlWJxvMfFBvtI5aC+M3QXsFGmxlZ4P95FUvczIasCipztDFqaP6orHP260c+4XwqKQGShUD5EJeiRF0CVphIPSLxZvN+QExGR86T59FvmCvRxTChDAzKXkageOwrZXk/7RuxOFJv1A2jwhWLhMNo+boeLkAPFMeJOoZASFpCEpyORZeSKQ12cxybSc26TxApCHQQ5NEZw8WptIZI2zWQ/iCuXeymB/wTtkkZU6BL/ggazUaeXt7wDfB+fFRm/DH48bpyWr4e+wJe8oOWZu9YKfsPTtjHSYTSL4m35LvlR+VX9Wd6u7StZKsYh6zDavW/wDtWhQE

!5

removeMin()

49

54

3

94

62

39

11

96 95 75 82 43 50 36

Broken heap

Calls: removeMin() 1

function removeMin last = last node in the tree minvalue = root swap root with last percolateDown(root) return minvalue

end function

AAADVnicbVLbbhMxEPUmlJZwS+GRF4ukUpFQlfSFviAqcREvSEWQtlISRV7vJLHqy8oeJ0SrfAGv8G/wM8BsLtCkjLTa43NmPBdPmmsVsNX6mVSqt3Zu7+7dqd29d//Bw/r+o/PgopfQkU47f5mKAFpZ6KBCDZe5B2FSDRfp1etSv5iAD8rZzzjLoW/EyKqhkgKJGtR/91IYKVsIPXJe4djMa9uMksS9i1aWEYUH4ybwQdl5QfQnFAi8qUXAJn/Jyz+3LgOuLMcxcPQAf72MshOhI5Cjdw6bayFMRc6bC4pPKePqvrWcg6c+Cb1xU3u49Hu2Fj1g9Pbf3RT11mbrams9sNlWJxvMfFBvtI5aC+M3QXsFGmxlZ4P95FUvczIasCipztDFqaP6orHP260c+4XwqKQGShUD5EJeiRF0CVphIPSLxZvN+QExGR86T59FvmCvRxTChDAzKXkageOwrZXk/7RuxOFJv1A2jwhWLhMNo+boeLkAPFMeJOoZASFpCEpyORZeSKQ12cxybSc26TxApCHQQ5NEZw8WptIZI2zWQ/iCuXeymB/wTtkkZU6BL/ggazUaeXt7wDfB+fFRm/DH48bpyWr4e+wJe8oOWZu9YKfsPTtjHSYTSL4m35LvlR+VX9Wd6u7StZKsYh6zDavW/wDtWhQE

!6

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download