{"id":101,"date":"2024-01-08T09:04:55","date_gmt":"2024-01-08T09:04:55","guid":{"rendered":"https:\/\/tensor.agenthub.uk\/?p=101"},"modified":"2024-01-08T09:05:25","modified_gmt":"2024-01-08T09:05:25","slug":"max-heap-sort","status":"publish","type":"post","link":"https:\/\/tensorzen.blog\/?p=101","title":{"rendered":"Max Heap Sort"},"content":{"rendered":"\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
#<\/span>include<\/span> <\/span><<\/span>iostream<\/span>><\/span><\/span>\n#<\/span>include<\/span> <\/span><<\/span>vector<\/span>><\/span><\/span>\n<\/span>\nusing<\/span> <\/span>std<\/span>::<\/span>vector<\/span>;<\/span><\/span>\nusing<\/span> <\/span>std<\/span>::<\/span>cout<\/span>;<\/span><\/span>\nusing<\/span> <\/span>std<\/span>::<\/span>swap<\/span>;<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>Heapify<\/span>(<\/span>vector<\/span><<\/span>int<\/span>>&<\/span> <\/span>arr<\/span>,<\/span> <\/span>int<\/span> <\/span>n<\/span>,<\/span> <\/span>int<\/span> <\/span>i<\/span>)<\/span>{<\/span><\/span>\n    <\/span>int<\/span> <\/span>largest<\/span> <\/span>=<\/span> <\/span>i<\/span>;<\/span> <\/span>\/\/ Initialize largest as root<\/span><\/span>\n    <\/span>int<\/span> <\/span>left<\/span> <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> <\/span>i<\/span> <\/span>+<\/span> <\/span>1<\/span>;<\/span> <\/span>\/\/ Left child<\/span><\/span>\n    <\/span>int<\/span> <\/span>right<\/span> <\/span>=<\/span> <\/span>2<\/span> <\/span>*<\/span> <\/span>i<\/span> <\/span>+<\/span> <\/span>2<\/span>;<\/span> <\/span>\/\/ Right child<\/span><\/span>\n<\/span>\n    <\/span>\/\/ If left child is larger than root<\/span><\/span>\n    <\/span>if<\/span>(<\/span>left<\/span> <\/span><<\/span> <\/span>n<\/span> <\/span>&&<\/span> <\/span>arr<\/span>[<\/span>left<\/span>] <\/span>><\/span> <\/span>arr<\/span>[<\/span>largest<\/span>]) <\/span>largest<\/span> <\/span>=<\/span> <\/span>left<\/span>;<\/span><\/span>\n    <\/span>\/\/ If right child is larger than largest so far<\/span><\/span>\n    <\/span>if<\/span>(<\/span>right<\/span> <\/span><<\/span> <\/span>n<\/span> <\/span>&&<\/span> <\/span>arr<\/span>[<\/span>right<\/span>] <\/span>><\/span> <\/span>arr<\/span>[<\/span>largest<\/span>]) <\/span>largest<\/span> <\/span>=<\/span> <\/span>right<\/span>;<\/span><\/span>\n<\/span>\n    <\/span>\/\/ If largest is not root<\/span><\/span>\n    <\/span>if<\/span>(<\/span>largest<\/span> <\/span>!=<\/span> <\/span>i<\/span>)<\/span>{<\/span><\/span>\n        <\/span>swap<\/span>(<\/span>arr<\/span>[<\/span>i<\/span>]<\/span>,<\/span> <\/span>arr<\/span>[<\/span>largest<\/span>])<\/span>;<\/span><\/span>\n        <\/span>\/\/ Recursively heapify the affected sub-tree<\/span><\/span>\n        <\/span>Heapify<\/span>(<\/span>arr<\/span>,<\/span> <\/span>n<\/span>,<\/span> <\/span>largest<\/span>)<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>HeapSort<\/span>(<\/span>vector<\/span><<\/span>int<\/span>>&<\/span> <\/span>arr<\/span>)<\/span>{<\/span><\/span>\n    <\/span>int<\/span> <\/span>n<\/span> <\/span>=<\/span> <\/span>arr<\/span>.<\/span>size<\/span>()<\/span>;<\/span><\/span>\n    <\/span>\/\/ build max heap<\/span><\/span>\n    <\/span>\/\/ The parent of the ith element is at index i \/ 2 - 1.<\/span><\/span>\n    <\/span>\/\/ Therefore, the parent of the nth element is at index n \/ 2 - 1<\/span><\/span>\n    <\/span>for<\/span>(<\/span>int<\/span> <\/span>i<\/span> <\/span>=<\/span> <\/span>n<\/span> <\/span>\/<\/span> <\/span>2<\/span> <\/span>-<\/span> <\/span>1<\/span>;<\/span> <\/span>i<\/span> <\/span>>=<\/span> <\/span>0<\/span>;<\/span> <\/span>i<\/span>--<\/span>) <\/span>Heapify<\/span>(<\/span>arr<\/span>,<\/span> <\/span>n<\/span>,<\/span> <\/span>i<\/span>)<\/span>;<\/span><\/span>\n    <\/span>\/\/ One by one extract an element from heap<\/span><\/span>\n    <\/span>for<\/span>(<\/span>int<\/span> <\/span>i<\/span> <\/span>=<\/span> <\/span>n<\/span> <\/span>-<\/span> <\/span>1<\/span>;<\/span> <\/span>i<\/span> <\/span>><\/span> <\/span>0<\/span>;<\/span> <\/span>i<\/span>--<\/span>)<\/span>{<\/span><\/span>\n        <\/span>\/\/ Move current root to end<\/span><\/span>\n        <\/span>swap<\/span>(<\/span>arr<\/span>[<\/span>0<\/span>]<\/span>,<\/span> <\/span>arr<\/span>[<\/span>i<\/span>])<\/span>;<\/span><\/span>\n        <\/span>\/\/ Call max heapify on the reduced heap (re-build max heap)<\/span><\/span>\n        <\/span>Heapify<\/span>(<\/span>arr<\/span>,<\/span> <\/span>i<\/span>,<\/span> <\/span>0<\/span>)<\/span>;<\/span><\/span>\n    <\/span>}<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nvoid<\/span> <\/span>PrintArray<\/span>(<\/span>const<\/span> <\/span>vector<\/span><<\/span>int<\/span>>&<\/span> <\/span>arr<\/span>)<\/span>{<\/span><\/span>\n    <\/span>for<\/span>(<\/span>int<\/span> <\/span>i<\/span> : <\/span>arr<\/span>)<\/span><\/span>\n        <\/span>cout<\/span> <\/span><<<\/span> <\/span>i<\/span> <\/span><<<\/span> <\/span>"<\/span> <\/span>"<\/span>;<\/span><\/span>\n    <\/span>cout<\/span> <\/span><<<\/span> <\/span>"<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n}<\/span><\/span>\n<\/span>\nint<\/span> <\/span>main<\/span>()<\/span>{<\/span><\/span>\n    <\/span>vector<\/span><<\/span>int<\/span>><\/span> <\/span>arr<\/span> <\/span>=<\/span> <\/span>{<\/span>4<\/span>,<\/span> <\/span>6<\/span>,<\/span> <\/span>8<\/span>,<\/span> <\/span>5<\/span>,<\/span> <\/span>9<\/span>}<\/span>;<\/span><\/span>\n    <\/span>cout<\/span> <\/span><<<\/span> <\/span>"<\/span>Original Array:<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n    <\/span>PrintArray<\/span>(<\/span>arr<\/span>)<\/span>;<\/span><\/span>\n    <\/span>HeapSort<\/span>(<\/span>arr<\/span>)<\/span>;<\/span><\/span>\n    <\/span>cout<\/span> <\/span><<<\/span> <\/span>"<\/span>Sorted Array:<\/span>\\n<\/span>"<\/span>;<\/span><\/span>\n    <\/span>PrintArray<\/span>(<\/span>arr<\/span>)<\/span>;<\/span><\/span>\n    <\/span>return<\/span> <\/span>0<\/span>;<\/span><\/span>\n}<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
\"\"<\/figure>\n\n\n\n
A max-heap viewed as (a) a binary tree and (b) an arry.  The root of the tree is A[1], and given the index i of a node, there’s a simple way to compute the indices of it’s parent, left child, and right child with the one-line procedures PARENT, LEFT, and RIGHT:<\/p>\n\n\n\n
PARENT(i): $$\\left \\lfloor i \/ 2 \\right \\rfloor$$<\/p>\n\n\n\n
LEFT(i): $$\\left \\lfloor 2i \\right \\rfloor$$<\/p>\n\n\n\n
RIGHT(i): $$\\left \\lfloor 2i + 1 \\right \\rfloor$$<\/p>\n\n\n\n
There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satify a heap property, the specifics of which depend on the kind of heap. In max-heap, the max-heap property is that for every node i other than the root<\/p>\n\n\n\n
A[PARENT(i)] >= A[i]<\/p>\n\n\n\n
that is, the value of a node is at most the value of its parent. Thus, the largest value in a max-heap is stored at the root, the subtree rooted at a node<\/mark> contains values no larger than<\/mark> that contained at the node itself<\/mark>. A min-heap is organized in the opposite way: the min-heap property is that for every node i other than the root,<\/p>\n\n\n\n
A[PARENT(i)] <= A[i]<\/p>\n\n\n\n
<\/p>\n\n\n\n
MAX-HEAPIFY:<\/h2>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
The action of MAX-HEAPIFY(A, 2), where, A.heap-size = 10. <\/p>\n\n\n\n
BUILD-MAX-HEAP<\/h2>\n\n\n\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n\n\n\n
The operation of BUILD-MAX-HEAP, showing the data structure before the call to MAX-HEAPIFY in line 3 of BUILD-MAX-HEAP.<\/p>\n","protected":false},"excerpt":{"rendered":"
A max-heap viewed as (a) a binary tree and (b) an arry. The root of the tree is A[1], and given the index i of a node, there’s […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-101","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/tensorzen.blog\/index.php?rest_route=\/wp\/v2\/posts\/101","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/tensorzen.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/tensorzen.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/tensorzen.blog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/tensorzen.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=101"}],"version-history":[{"count":2,"href":"https:\/\/tensorzen.blog\/index.php?rest_route=\/wp\/v2\/posts\/101\/revisions"}],"predecessor-version":[{"id":108,"href":"https:\/\/tensorzen.blog\/index.php?rest_route=\/wp\/v2\/posts\/101\/revisions\/108"}],"wp:attachment":[{"href":"https:\/\/tensorzen.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=101"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/tensorzen.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=101"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/tensorzen.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=101"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}