{"id":123,"date":"2021-12-02T11:12:34","date_gmt":"2021-12-02T03:12:34","guid":{"rendered":"http:\/\/purplepoolobservatory.com\/?p=123"},"modified":"2021-12-03T08:52:51","modified_gmt":"2021-12-03T00:52:51","slug":"heapsort%e5%bf%ab%e9%80%9f%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"https:\/\/purplepoolobservatory.com\/?p=123","title":{"rendered":"heapsort\u5feb\u901f\u6392\u5e8f"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>void sort(float arr&#91;], unsigned int N)\n  { \/\/ heapsort algorithm\n      unsigned int n = N, i = n\/2, parent, child;\n      int t;\n\n      for (;;) { \/* Loops until arr is sorted *\/\n          if (i > 0) { \/* First stage - Sorting the heap *\/\n              i--;           \/* Save its index to i *\/\n              t = arr&#91;i];    \/* Save parent value to t *\/\n          } else {     \/* Second stage - Extracting elements in-place *\/\n              n--;           \/* Make the new heap smaller *\/\n              if (n == 0) return; \/* When the heap is empty, we are done *\/\n              t = arr&#91;n];    \/* Save last value (it will be overwritten) *\/\n              arr&#91;n] = arr&#91;0]; \/* Save largest value at the end of arr *\/\n          }\n\n          parent = i; \/* We will start pushing down t from parent *\/\n          child = i*2 + 1; \/* parent's left child *\/\n\n          \/* Sift operation - pushing the value of t down the heap *\/\n          while (child &lt; n) {\n              if (child + 1 &lt; n  &amp;&amp;  arr&#91;child + 1] > arr&#91;child]) {\n                  child++; \/* Choose the largest child *\/\n              }\n              if (arr&#91;child] > t) { \/* If any child is bigger than the parent *\/\n                  arr&#91;parent] = arr&#91;child]; \/* Move the largest child up *\/\n                  parent = child; \/* Move parent pointer to this child *\/\n                  \/\/child = parent*2-1; \/* Find the next child *\/\n                  child = parent*2+1; \/* the previous line is wrong*\/\n              } else {\n                  break; \/* t's place is found *\/\n              }\n          }\n          arr&#91;parent] = t; \/* We save t in the heap *\/\n      }\n  }<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"gallery","meta":{"footnotes":""},"categories":[2],"tags":[9,6],"class_list":["post-123","post","type-post","status-publish","format-gallery","hentry","category-technology","tag-c","tag-linux","post_format-post-format-gallery"],"_links":{"self":[{"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=\/wp\/v2\/posts\/123","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=123"}],"version-history":[{"count":1,"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions"}],"predecessor-version":[{"id":124,"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions\/124"}],"wp:attachment":[{"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=123"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/purplepoolobservatory.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}