{"id":867,"date":"2018-07-17T18:19:15","date_gmt":"2018-07-17T10:19:15","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=867"},"modified":"2018-07-17T18:19:15","modified_gmt":"2018-07-17T10:19:15","slug":"%e7%ac%ac%e5%8d%81%e4%ba%94%e8%ae%b2%ef%bc%9a%e5%a0%86","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/python\/867\/","title":{"rendered":"\u7b2c\u5341\u4e94\u8bb2\uff1a\u5806"},"content":{"rendered":"<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\"># -*- coding:utf-8 -*-\n# \u5806\nclass Heap(object):\n    def __init__(self):\n        self.dataList = [None]      # \u7b2c\u4e00\u4e2a\u5143\u7d20\u8bbe\u4e3a None \u907f\u514d 0 \u4e0b\u6807\n    def size(self):\n        return len(self.dataList) - 1\n    def leftChild(self, root):\n        return root * 2\n    def rightChild(self, root):\n        return root * 2 + 1\n    def father(self, node):\n        return node \/ 2\n    def heapify(self, root):\n        if root &gt; self.size():\n            return\n        leftNode = self.leftChild(root)\n        rightNode = self.rightChild(root)\n        largest = root\n        if leftNode &lt;= self.size():     # \u9632\u6b62\u8fd9\u4e2a\u70b9\u662f\u53f6\u5b50\u7ed3\u70b9\n            if self.dataList[leftNode] &gt; self.dataList[largest]:\n                largest = leftNode\n        if rightNode &lt;= self.size():     # \u9632\u6b62\u8fd9\u4e2a\u70b9\u662f\u53f6\u5b50\u7ed3\u70b9\n            if self.dataList[rightNode] &gt; self.dataList[largest]:\n                largest = rightNode\n        if largest != root:\n            self.dataList[root], self.dataList[largest] = self.dataList[largest], self.dataList[root]\n            self.heapify(largest)\n    def buildHeap(self):\n        for i in range(self.size() \/ 2, 0, -1):  # \u4ece\u6700\u540e\u4e00\u4e2a\u975e\u53f6\u5b50\u7ed3\u70b9\u904d\u5386\n            self.heapify(i)\n    def getMax(self):\n        if self.size() == 0:  # \u5224\u65ad\u5806\u662f\u5426\u4e3a\u7a7a\n            return None\n        ret = self.dataList[1]  # \u4fdd\u5b58\u5806\u9876\u5143\u7d20\n        self.dataList[1] = self.dataList[-1]  # \u628a\u6700\u540e\u4e00\u4f4d\u79fb\u5230\u7b2c\u4e00\u4f4d\n        del self.dataList[-1]  # \u5220\u9664\u6700\u540e\u4e00\u4f4d\n        self.heapify(1)  # \u91cd\u65b0\u5efa\u5806\n        return ret\n    def insert(self, data):\n        self.dataList.append(data)  # \u5b58\u5230\u6700\u540e\u9762\n        nowIndex = self.size()  # \u62ff\u5230\u4e0b\u6807\uff08\u5c31\u662f\u957f\u5ea6\uff09\n        pre = self.father(nowIndex)  # \u62ff\u5230\u7236\u4eb2\u8282\u70b9\u4e0b\u6807\n        while self.dataList[pre] &lt; data and nowIndex != 1:  # \u904d\u5386\u7236\u8282\u70b9 \u76f4\u5230\u4e3a\u6839\u7ed3\u70b9\u6216\u8005\u7236\u8282\u70b9\u6bd4data\u5927\n            self.dataList[pre], self.dataList[nowIndex] = self.dataList[nowIndex], self.dataList[pre]\n            nowIndex = pre\n            pre = nowIndex \/ 2\nheap = Heap()\nheap.insert(9)\nheap.insert(10)\nheap.insert(7)\nheap.insert(12)\nheap.insert(3)\nheap.insert(4)\n# print heap.getMax()\n# print heap.getMax()\n# print heap.getMax()\n# print heap.getMax()\n# print heap.getMax()\n# print heap.getMax()\n# print heap.getMax()\nheap.insert(9)\nheap.insert(8)\nheap.insert(7)\nheap.insert(7)\nheap.insert(12)\n# print heap.getMax()\nheap.dataList = [None, 1, 2, 3, 4, 5, 6, 7]\nheap.buildHeap()\n# print heap.getMax()\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p># -*- coding:utf-8 -*- # \u5806 class Heap(object): def [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[24],"tags":[],"views":3867,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/867"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=867"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/867\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=867"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=867"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=867"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}