DOC PREVIEW
SJSU CS 146 - Heapsort

This preview shows page 1-2-3-4 out of 13 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 13 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

HeapsortOverview:What is a Heap?Example:AlgorithmSimplifying thingsSlide 7Sample RunSlide 9Step 2 – perform n – 1 deleteMax(es), and replace last element in heap with first, then re-heapify. Place deleted element in the last nodes position.Slide 11Slide 12ConclusionHeapsortBy Pedro OñateCS-146Dr. Sin-Min LeeOverview:•Uses a heap as its data structure•In-place sorting algorithm – memory efficient•Time complexity – O(n log(n))What is a Heap?A heap is also known as a priority queue and can be represented by a binary tree with the following properties:Structure property: A heap is a completely filled binary tree with the exception of the bottom row, which is filled from left to right Heap Order property: For every node x in the heap, the parent of x greater than or equal to the value of x.(known as a maxHeap).Example:5344 2515 21 13 183 12 5 7a heapAlgorithmStep 1. Build Heap – O(n)- Build binary tree taking N items as input, ensuring the heap structure property is held, in other words, build a complete binary tree. - Heapify the binary tree making sure the binary tree satisfies the Heap Order property.Step 2. Perform n deleteMax operations – O(log(n))- Delete the maximum element in the heap – which is the root node, and place this element at the end of the sorted array.Simplifying things•For speed and efficiency we can represent the heap with an array. Place the root at array index 1, its left child at index 2, its right child at index 3, so on and so forth…5344 2515 21 13 183 12 5 7 0 1 2 3 4 5 6 7 8 9 10 1153 44 25 15 21 13 18 3 12 5 75344 2515 21 13 183 12 5 7 0 1 2 3 4 5 6 7 8 9 10 1153 44 25 15 21 13 18 3 12 5 7For any node i, the following formulas apply:The index of its parent = i / 2Index of left child = 2 * iIndex of right child = 2 * i + 1Sample Run•Start with unordered array of dataArray representation:Binary tree representation:21 15 25 3 5 12 7 19 45 2 92115 253 5 12 719 45 2 9Sample Run•Heapify the binary tree - 2115 253 5 12 719 45 2 92115 253 9 12 719 45 2 52115 2545 9 12 719 3 2 52115 2545 9 12 719 3 2 52145 2519 9 12 715 3 2 54521 2519 9 12 715 3 2 5Step 2 – perform n – 1 deleteMax(es), and replace last element in heap with first, then re-heapify. Place deleted element in the last nodes position.4521 2519 9 12 715 3 2 545 21 25 19 9 12 7 15 3 2 52521 1219 9 5 715 3 225 21 12 19 9 5 7 15 3 2 452521 1219 9 5 715 3 225 21 12 19 9 5 7 15 3 2 452119 1215 9 5 72 321 19 12 15 9 5 7 2 3 25 452119 1215 9 5 72 321 19 12 15 9 5 7 2 3 25 451915 123 9 5 7219 15 12 3 9 5 7 2 21 25 451915 123 9 5 7219 15 12 3 9 5 7 2 21 25 45159 123 2 5 715 9 12 3 2 5 7 19 21 25 45159 123 2 5 715 9 12 3 2 5 7 19 21 25 45129 73 2 512 9 7 3 2 5 15 19 21 25 45129 73 2 512 9 7 3 2 5 15 19 21 25 4595 73 29 5 7 3 2 12 15 19 21 25 45…and finally22 3 5 7 9 12 15 19 21 25 45Conclusion•1st Step- Build heap, O(n) time complexity•2nd Step – perform n deleteMax operations, each with O(log(n)) time complexity•total time complexity = O(n log(n))•Pros: fast sorting algorithm, memory efficient, especially for very large values of n.•Cons: slower of the O(n log(n)) sorting


View Full Document

SJSU CS 146 - Heapsort

Download Heapsort
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Heapsort and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Heapsort 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?