{"id":779,"date":"2020-12-16T15:45:34","date_gmt":"2020-12-16T07:45:34","guid":{"rendered":"http:\/\/www.mustenaka.cn\/?p=779"},"modified":"2020-12-16T15:46:08","modified_gmt":"2020-12-16T07:46:08","slug":"heapsortcode","status":"publish","type":"post","link":"https:\/\/www.mustenaka.cn\/index.php\/2020\/12\/16\/heapsortcode\/","title":{"rendered":"\u5806\u6392\u5e8f\u4ee3\u7801"},"content":{"rendered":"<h1>\u5806\u6392\u5e8f<\/h1>\n<p>\u7b49\u6211\u8003\u5b8c\u4e86\u518d\u8865\u8fd9\u4e2a\u535a\u5ba2\u7684\u5177\u4f53\u5185\u5bb9\u3002<\/p>\n<p>\u5806\u6392\u5e8f\u6709\u5982\u4e0b\u51e0\u4e2a\u7279\u5f81<\/p>\n<ul>\n<li>\u5806\u662f\u4e00\u4e2a\u5b8c\u5168\u4e8c\u53c9\u6811\uff0c\u6784\u9020\u751f\u5b58\uff0c\u5220\u9664\u90fd\u8981\u6309\u7167\u5b8c\u5168\u4e8c\u53c9\u6811\u7684\u89c4\u5219\u8fdb\u884c<\/li>\n<li>\u6240\u6709\u7236\u8282\u70b9\u7684\u503c\u90fd\u5fc5\u987b\u8981\u5927\u4e8e\uff08\u6216\u8005\u5c0f\u4e8e\uff09\u5b50\u7ed3\u70b9\u7684\u503c<\/li>\n<li>\u4e3a\u4e86\u65b9\u4fbf\u5b9e\u73b0\u53ef\u4ee5\u7528\u6570\u7ec4\u6a21\u62df\u4ee3\u66ff\u5b8c\u5168\u4e8c\u53c9\u6811\u7684\u6784\u5efa<\/li>\n<\/ul>\n<p>\u5bf9\u4e8e\u4e00\u9897\u5b8c\u5168\u4e8c\u53c9\u6811\uff0c\u5728\u8fdb\u884c\u6a21\u62df\u7684\u65f6\u5019\uff0c\u8bbe\u5f53\u524d\u7ed3\u70b9\u4e3ai\uff0c\u5219\u6709<\/p>\n<ul>\n<li>\u5176\u7236\u7ed3\u70b9parent = (i &#8211; 1) \/ 2<\/li>\n<li>\u5176\u5de6\u5b69\u5b50 left_c = (i * 2) + 1<\/li>\n<li>\u5176\u53f3\u5b69\u5b50 right_c = (i * 2) + 2<\/li>\n<\/ul>\n<p>\u5806\u6392\u5e8f\u4ee3\u7801\uff0c\u5206\u4e3a\uff0c<\/p>\n<ul>\n<li>heapify\u5806\u5316\uff0c\u6b63\u5bf9\u4e00\u4e2a\u7ed3\u70b9\u7684\u5806\u5316\uff0c<\/li>\n<li>build_heap\uff0c\u6784\u5efa\u5806\uff0c\u5c06\u6574\u4e2a\u6570\u7ec4\u5806\u5316\uff08\u6279\u91cf\u8c03\u7528heapify\uff09<\/li>\n<li>heap_sort\uff0c\u5229\u7528\u5806\u8fdb\u884c\u7684\u5806\u6392\u5e8f<\/li>\n<\/ul>\n<h3>\u4ee3\u7801\u5982\u4e0b<\/h3>\n<pre class=\"pure-highlightjs\"><code class=\"\" cpp=\"\">#include&lt;stdio.h&gt;\r\n\r\nvoid swap(int arr[], int i, int j) {\r\n\tint temp = arr[i];\r\n\tarr[i] = arr[j];\r\n\tarr[j] = temp;\r\n}\r\n\r\nvoid heapify(int tree[], int n, int i){\r\n\tint max = i;\r\n\tint c1 = 2 * i + 1;\r\n\tint c2 = 2 * i + 2;\r\n\tif (c1 &lt; n &amp;&amp; tree[c1] &gt; tree[max]) {\r\n\t\tmax = c1;\r\n\t}\r\n\tif (c2 &lt; n &amp;&amp; tree[c2] &gt; tree[max]) {\r\n\t\tmax = c2;\r\n\t}\r\n\tif(max != i){\r\n\t\tswap(tree, max, i);\r\n\t\theapify(tree, n ,max);\r\n\t}\r\n}\r\n\r\nvoid build_heap(int tree[], int n){\r\n\tint last_node = n - 1;\r\n\tint parent = (last_node - 1) \/ 2;\r\n\tint i;\r\n\tfor (i = parent; i &gt;= 0; i--) {\r\n\t\theapify(tree, n, i);\r\n\t}\r\n}\r\n\r\nvoid heap_sort(int tree[], int n) {\r\n\tbuild_heap(tree, n);\r\n\tint i;\r\n\tfor (i = n - 1; i &gt;= 0; i--){\r\n\t\tswap(tree, i ,0);\r\n\t\theapify(tree, i, 0);\r\n\t}\r\n}\r\n\r\nint main(){\r\n\tint tree[] = {2, 10, 3, 1, 5, 4};\r\n\tint n = 6;\r\n\theap_sort(tree, n);\r\n\t\r\n\tint i;\r\n\tfor(i = 0; i &lt; n; i++){\r\n\t\tprintf(\"%d\\n\",tree[i]);\r\n\t}\r\n\treturn 0;\r\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u5806\u6392\u5e8f \u7b49\u6211\u8003\u5b8c\u4e86\u518d\u8865\u8fd9\u4e2a\u535a\u5ba2\u7684\u5177\u4f53\u5185\u5bb9\u3002 \u5806\u6392\u5e8f\u6709\u5982\u4e0b\u51e0\u4e2a\u7279\u5f81 \u5806\u662f\u4e00\u4e2a\u5b8c\u5168\u4e8c\u53c9\u6811\uff0c\u6784\u9020\u751f\u5b58\uff0c\u5220\u9664 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,45],"tags":[33],"class_list":["post-779","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c","tag-c"],"views":1013,"_links":{"self":[{"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/posts\/779","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/comments?post=779"}],"version-history":[{"count":1,"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/posts\/779\/revisions"}],"predecessor-version":[{"id":780,"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/posts\/779\/revisions\/780"}],"wp:attachment":[{"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/media?parent=779"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/categories?post=779"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mustenaka.cn\/index.php\/wp-json\/wp\/v2\/tags?post=779"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}