{"id":209,"date":"2013-06-17T20:24:29","date_gmt":"2013-06-17T12:24:29","guid":{"rendered":"http:\/\/coderbee.net\/?p=209"},"modified":"2014-11-28T20:32:29","modified_gmt":"2014-11-28T12:32:29","slug":"%e5%a0%86%e6%8e%92%e5%ba%8f","status":"publish","type":"post","link":"https:\/\/coderbee.net\/index.php\/algorithm\/20130617\/209","title":{"rendered":"\u5806\u6392\u5e8f"},"content":{"rendered":"<h2>\u5806\u6392\u5e8f<\/h2>\n<p>\u8fd9\u91cc\u7684\u5806\u4e0d\u662f\u7f16\u7a0b\u8bed\u8a00\u91cc\u7684\u5806\uff0c\u662f\u4e00\u79cd\u6570\u636e\u7ed3\u6784\u3002<\/p>\n<p>\u5806\u50cf\u4e00\u68f5\u5012\u7acb\u7684\u6ee1\u4e8c\u53c9\u6811\uff0c\u6bcf\u4e2a\u8282\u70b9\u6700\u591a\u6709\u4e24\u4e2a\u76f4\u63a5\u5b50\u8282\u70b9\u3002\u6700\u4e0a\u9762\u7684\u8282\u70b9\u79f0\u4e3a\u6839\u8282\u70b9\uff0c\u6ca1\u6709\u5b50\u8282\u70b9\u7684\u8282\u70b9\u79f0\u4e3a\u53f6\u5b50\u8282\u70b9\uff0c\u6709\u5b50\u8282\u70b9\u7684\u8282\u70b9\u79f0\u4e3a\u5206\u652f\u8282\u70b9\u3002<\/p>\n<p>\u5806\u6709\u5927\u9876\u5806\u548c\u5c0f\u9876\u5806\u4e4b\u5206\u3002\u5927\u9876\u5806\u662f\u6307\u5206\u652f\u8282\u70b9\u5927\u4e8e\u5b83\u7684\u6240\u6709\u5b50\u8282\u70b9\uff0c\u5806\u91cc\u6700\u5927\u5143\u7d20\u662f\u6839\u8282\u70b9\uff1b\u5c0f\u9876\u5806\u662f\u6307\u5206\u652f\u8282\u70b9\u5c0f\u4e8e\u5b83\u7684\u6240\u6709\u5b50\u8282\u70b9\uff0c\u5806\u91cc\u6700\u5c0f\u5143\u7d20\u662f\u6839\u8282\u70b9\u3002<\/p>\n<p>\u5806\u6392\u5e8f\u662f\u501f\u52a9\u5806\u6570\u636e\u7ed3\u6784\u8fdb\u884c\u6392\u5e8f\u7684\u4e00\u79cd\u9ad8\u6548\u7b97\u6cd5\uff0c\u5b83\u7684\u5e73\u5747\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(n*lg(n))\u3002<\/p>\n<h3>\u5b9e\u73b0<\/h3>\n<p>\u5806\u6392\u5e8f\u7684\u6838\u5fc3\u662f\u6784\u5efa\u548c\u7ef4\u6301\u5806\u3002<\/p>\n<p>\u5b9e\u73b0\u65f6\u8981\u6ce8\u610f\u7684\u662f\uff1a<\/p>\n<ul>\n<li>\n<p>\u4ee5\u6570\u7ec4\u7b2c\u4e00\u4e2a\u8282\u70b9\uff08\u5e8f\u53f7\u4e3a0\uff09\u4e3a\u6839\uff0c\u65b9\u4fbf\u8ba1\u7b97\u53f6\u5b50\u8282\u70b9\u3002<\/p>\n<\/li>\n<li>\n<p>\u5927\u591a\u6570\u7b97\u6cd5\u4ecb\u7ecd\u90fd\u662f\u4ee5<code>1<\/code>\u4e3a\u6570\u7ec4\u7684\u8d77\u59cb\u4e0b\u6807\u7684\uff0c\u5de6\u53f3\u53f6\u5b50\u8282\u70b9\u7684\u8ba1\u7b97\u5206\u522b\u4e3a\uff1a<code>lchild=2*parent; rchild =2*parent+1<\/code>\uff1b\u800c\u5b9e\u9645\u7f16\u7a0b\u8bed\u8a00\u5927\u591a\u6570\u90fd\u662f\u4ee5<code>0<\/code>\u4e3a\u8d77\u59cb\u4e0b\u6807\u7684\uff0c\u6240\u4ee5\u5b50\u8282\u70b9\u8ba1\u7b97\u9700\u8981\u8c03\u6574\u4e3a\uff1a<code>lchild=2*parent+1;  rchild=2*parent+2<\/code>\uff1b\u56e0\u4e3a\u6839\u8282\u70b9\u662f0\uff0c\u5bfc\u81f4\u6839\u8282\u70b9\u7684\u5de6\u5b50\u6811\u4e0e\u6839\u8282\u70b9\u76f8\u540c\u800c\u51fa\u9519\u3002<\/p>\n<\/li>\n<li>\n<p>\u6784\u5efa\u662f\u4ece\u5e95\u5411\u4e0a\u9010\u5c42\u6784\u5efa\u5806\uff0c\u4ece\u6700\u540e\u4e00\u5c42\u7684\u5206\u652f\u8282\u70b9\uff08 <code>len(arr)\/2<\/code> \uff09\u5f00\u59cb\u6784\u5efa\u5806\u3002<\/p>\n<\/li>\n<li>\n<p>\u4ece\u5806\u9876\u53d6\u51fa\u6700\u5927\u5143\u7d20\u4e0e\u6700\u540e\u4e00\u4e2a\u5806\u5143\u7d20\u4ea4\u4e92\u540e\uff0c\u5806\u7684\u5927\u5c0f\u51cf1\u3002\u6240\u4ee5\u5806\u5728\u6392\u5e8f\u8fc7\u7a0b\u4e2d\u662f\u9010\u6e10\u7f29\u5c0f\u7684\uff0c\u4f46\u6839\u603b\u662f\u7b2c\u4e00\u4e2a\u5143\u7d20\uff0c\u6240\u4ee5\u53ef\u4ee5\u5229\u7528\u4e4b\u524d\u4e5f\u6784\u5efa\u597d\u7684\u5806\uff0c\u53ea\u9700\u8981\u8c03\u6574\u4e00\u68f5\u5b50\u6811\u3002<br \/>\n<!--more--><\/p>\n<\/li>\n<\/ul>\n<pre><code language=\"go\">\nfunc left(parent int) int {\n    return 2*parent + 1\n}\n\nfunc right(parent int) int {\n    return 2*parent + 2\n}\n\nfunc MaxHeapify(arr []int, parent, heapSize int) {\n    l, r, largest := left(parent), right(parent), parent\n    if l < heapSize &#038;&#038; arr[l] > arr[parent] {\n        largest = l\n    }\n\n    if r < heapSize &#038;&#038; arr[r] > arr[largest] {\n        largest = r\n    }\n\n    if largest != parent {\n        util.Swap(arr, parent, largest)\n        MaxHeapify(arr, largest, heapSize)\n    }\n}\n\nfunc BuildMaxHeap(arr []int) {\n    for i, heapSize := len(arr)\/2, len(arr); i >= 0; i-- {\n        MaxHeapify(arr, i, heapSize)\n    }\n}\n\nfunc HeapSort(arr []int) {\n    BuildMaxHeap(arr)\n    for i := len(arr) - 1; i > 0; i-- {\n        util.Swap(arr, 0, i)\n        MaxHeapify(arr, 0, i)\n    }\n}\n<\/code><\/pre>\n<hr\/>\n<p>\u6b22\u8fce\u5173\u6ce8\u6211\u7684\u5fae\u4fe1\u516c\u4f17\u53f7: <strong>coderbee\u7b14\u8bb0<\/strong>\uff0c\u53ef\u4ee5\u66f4\u53ca\u65f6\u56de\u590d\u4f60\u7684\u8ba8\u8bba\u3002<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" width=\"258\" height=\"258\" src=\"https:\/\/coderbee.net\/wp-content\/uploads\/2019\/01\/coderbee-note.jpg\" class=\"alignnone size-full wp-image-1707\"><\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u5806\u6392\u5e8f \u8fd9\u91cc\u7684\u5806\u4e0d\u662f\u7f16\u7a0b\u8bed\u8a00\u91cc\u7684\u5806\uff0c\u662f\u4e00\u79cd\u6570\u636e\u7ed3\u6784\u3002 \u5806\u50cf\u4e00\u68f5\u5012\u7acb\u7684\u6ee1\u4e8c\u53c9\u6811\uff0c\u6bcf &hellip; <a href=\"https:\/\/coderbee.net\/index.php\/algorithm\/20130617\/209\">\u7ee7\u7eed\u9605\u8bfb <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[53],"tags":[55,56],"_links":{"self":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/209"}],"collection":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/comments?post=209"}],"version-history":[{"count":4,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/209\/revisions"}],"predecessor-version":[{"id":1108,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/posts\/209\/revisions\/1108"}],"wp:attachment":[{"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/media?parent=209"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/categories?post=209"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/coderbee.net\/index.php\/wp-json\/wp\/v2\/tags?post=209"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}