{"id":5930,"date":"2022-08-31T12:38:05","date_gmt":"2022-08-31T07:08:05","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/"},"modified":"2022-08-31T12:38:05","modified_gmt":"2022-08-31T07:08:05","slug":"solved-heap-sort-doesnt-work-properly","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/","title":{"rendered":"[Solved] Heap Sort doesn’t work properly"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

In the comments, you mention that you’re using array indexes in the interval 1..N<\/code> for an array of size N+1<\/code>, but the size you pass in is N+1<\/code>. If that’s true, you have an off-by-one error in max-heapify()<\/code>: if size<\/code> is N+1<\/code>, the last position you can access is N<\/code>, not N+1<\/code>, so you must change the comparison to l < size<\/code> (and similarly for r<\/code>):<\/p>\n

void heap_heapify(int *array, int size, int i) {\n    int largest, temp, \n        l = 2 * i, r = (2 * i) + 1;\n\n    if(l < size && array[l] > array[i])\n        largest = l;\n    else \n        largest = i;\n\n    if(r < size && array[r] > array[largest])\n        largest = r;\n\n    if(largest != i) {\n        temp = array[largest];\n        array[largest] = array[i];\n        array[i] = temp;\n        heap_heapify(array, size, largest);\n    }\n}\n<\/code><\/pre>\n
Alternatively, if you want to keep your code as close as possible to CLRS, you can use <=<\/code> as long as you pass N<\/code> as the size rather than N+1<\/code> (so, you allocate an array of N+1<\/code> elements, but you pass N<\/code> as the size, so things line up).<\/p>\n
[Side note: it has always bugged me that CLRS uses arrays indexed from 1. This always causes trouble when writing real code based on the pseudocode there].<\/p>\n
The same happens in heap_sort()<\/code>, either you pass it N<\/code> as size for an array of N+1<\/code> elements or you initialize i<\/code> to size-1<\/code>:<\/p>\n
void heap_sort(int *array, int size) {\n    int temp;\n\n    heap_build(array, size);\n\n    for(int i = size-1; i>1; i--) {\n        temp = array[i];\n        array[i] = array[1];\n        array[1] = temp;\n        size--;\n        heap_heapify(array, size, 1);\n    }\n}\n<\/code><\/pre>\n
Here’s a full program with the working code:<\/p>\n
#include <stdio.h>\n\nvoid heap_build(int *array, int size);\nvoid heap_heapify(int *array, int size, int i);\n\nvoid heap_sort(int *array, int size) {\n    int temp;\n\n    heap_build(array, size);\n\n    for(int i = size-1; i>1; i--) {\n        temp = array[i];\n        array[i] = array[1];\n        array[1] = temp;\n        size--;\n        heap_heapify(array, size, 1);\n    }\n}\n\nvoid heap_build(int *array, int size) {\n    for(int i = size \/ 2; i > 0; i--)\n        heap_heapify(array, size, i);\n}\n\nvoid heap_heapify(int *array, int size, int i) {\n    int largest, temp, \n        l = 2 * i, r = (2 * i) + 1;\n\n    if(l < size && array[l] > array[i])\n        largest = l;\n    else \n        largest = i;\n\n    if(r < size && array[r] > array[largest])\n        largest = r;\n\n    if(largest != i) {\n        temp = array[largest];\n        array[largest] = array[i];\n        array[i] = temp;\n        heap_heapify(array, size, largest);\n    }\n}\n\nint main(void) {\n    int arr[] = { 0, -22, 2, -33, 82, 71, 82, 0, -68, -59, -17, -8, 43, 59, -100 };\n\n    heap_sort(arr, sizeof(arr)\/sizeof(arr[0]));\n\n    for (int i = 0; i < sizeof(arr)\/sizeof(arr[0]); i++) {\n        printf(\"%d\\n\", arr[i]);\n    }\n\n    return 0;\n}\n<\/code><\/pre>\n
This prints:<\/p>\n
0\n-100\n-68\n-59\n-33\n-22\n-17\n-8\n0\n2\n43\n59\n71\n82\n82\n<\/code><\/pre>\n
Note that the first element is never sorted; since you use indexes 1..N<\/code>, you’re basically ignoring element 0. A quick hack is to pass in a pointer to one element before the start of the array, but that is ugly, and UB (pointer arithmetic is valid only if the resulting pointer references an element in the array, or one past the end).<\/p>\n
So I suggest refactoring the code and forget about 1-based indexing. This can be done by adjusting the formulas to calculate the left and right child of a node and adjusting the loop conditions:<\/p>\n
#include <stdio.h>\n\nvoid heap_build(int *array, int size);\nvoid heap_heapify(int *array, int size, int i);\n\nvoid heap_sort(int *array, int size) {\n    int temp;\n\n    heap_build(array, size);\n\n    for(int i = size-1; i > 0; i--) {\n        temp = array[i];\n        array[i] = array[0];\n        array[0] = temp;\n        size--;\n        heap_heapify(array, size, 0);\n    }\n}\n\nvoid heap_build(int *array, int size) {\n    for(int i = size\/2; i >= 0; i--)\n        heap_heapify(array, size, i);\n}\n\nvoid heap_heapify(int *array, int size, int i) {\n    int largest, temp,\n        l = i*2+1, r = l+1;\n\n    if (l < size && array[l] > array[i])\n        largest = l;\n    else \n        largest = i;\n\n    if (r < size && array[r] > array[largest])\n        largest = r;\n\n    if (largest != i) {\n        temp = array[largest];\n        array[largest] = array[i];\n        array[i] = temp;\n        heap_heapify(array, size, largest);\n    }\n}\n\nint main(void) {\n    int arr[] = { 0, -22, 2, -33, 82, 71, 82, 0, -68, -59, -17, -8, 43, 59, -100 };\n\n    heap_sort(arr, sizeof(arr)\/sizeof(arr[0]));\n\n    for (int i = 0; i < sizeof(arr)\/sizeof(arr[0]); i++) {\n        printf(\"%d\\n\", arr[i]);\n    }\n\n    return 0;\n}\n<\/code><\/pre>\n
The differences from the previous version are:<\/p>\n
    \n
  1. In heap_sort<\/code>, the loop condition turns into i > 0<\/code>.<\/li>\n
  2. In heap_build()<\/code>, the loop condition turns into i >= 0<\/code>.<\/li>\n
  3. In heap_heapify()<\/code>, the left child is 2*i+1<\/code> rather than 2*i<\/code>, and r<\/code> is 2*i+2<\/code>.<\/li>\n<\/ol>\n<\/div>\n
    <\/div>\n<\/div>\n
                5<\/span> <\/p><\/div>\n<\/div>\n
    [ad_2]<\/p>\n
    solved Heap Sort doesn’t work properly <\/p>\n","protected":false},"excerpt":{"rendered":"
    [ad_1] In the comments, you mention that you’re using array indexes in the interval 1..N for an array of size N+1, but the size you pass in is N+1. If that’s true, you have an off-by-one error in max-heapify(): if size is N+1, the last position you can access is N, not N+1, so you … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[324,1573,561],"class_list":["post-5930","post","type-post","status-publish","format-standard","hentry","category-solved","tag-c","tag-heapsort","tag-sorting"],"yoast_head":"\n[Solved] Heap Sort doesn't work properly - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Heap Sort doesn't work properly - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] In the comments, you mention that you’re using array indexes in the interval 1..N for an array of size N+1, but the size you pass in is N+1. If that’s true, you have an off-by-one error in max-heapify(): if size is N+1, the last position you can access is N, not N+1, so you ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-08-31T07:08:05+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Heap Sort doesn’t work properly\",\"datePublished\":\"2022-08-31T07:08:05+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/\"},\"wordCount\":295,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"c++\",\"heapsort\",\"sorting\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/\",\"name\":\"[Solved] Heap Sort doesn't work properly - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-08-31T07:08:05+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Heap Sort doesn’t work properly\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Heap Sort doesn't work properly - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Heap Sort doesn't work properly - JassWeb","og_description":"[ad_1] In the comments, you mention that you’re using array indexes in the interval 1..N for an array of size N+1, but the size you pass in is N+1. If that’s true, you have an off-by-one error in max-heapify(): if size is N+1, the last position you can access is N, not N+1, so you ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/","og_site_name":"JassWeb","article_published_time":"2022-08-31T07:08:05+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Heap Sort doesn’t work properly","datePublished":"2022-08-31T07:08:05+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/"},"wordCount":295,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["c++","heapsort","sorting"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/","url":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/","name":"[Solved] Heap Sort doesn't work properly - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-08-31T07:08:05+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-heap-sort-doesnt-work-properly\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Heap Sort doesn’t work properly"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1775798750","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/5930","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=5930"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/5930\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=5930"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=5930"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=5930"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}