{"id":7678,"date":"2020-11-18T01:30:19","date_gmt":"2020-11-18T09:30:19","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7678"},"modified":"2020-11-18T18:07:24","modified_gmt":"2020-11-19T02:07:24","slug":"min-heap-sp21","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sp\/min-heap-sp21\/","title":{"rendered":"\u82b1\u82b1\u9171 Min Heap SP21"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 Min Heap - \u5237\u9898\u627e\u5de5\u4f5c SP21\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/mnSMdTPBG1U?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-1.png\" alt=\"\" class=\"wp-image-7685\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-2.png\" alt=\"\" class=\"wp-image-7686\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-3.png\" alt=\"\" class=\"wp-image-7687\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-3-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-4.png\" alt=\"\" class=\"wp-image-7688\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-4-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-6.png\" alt=\"\" class=\"wp-image-7689\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-6.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-6-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-6-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-7.png\" alt=\"\" class=\"wp-image-7690\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-7.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-7-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-7-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-8.png\" alt=\"\" class=\"wp-image-7691\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-8.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-8-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-8-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-9.png\" alt=\"\" class=\"wp-image-7692\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-9.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-9-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/11\/sp21-9-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\n#include <assert.h>\n\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nclass MinHeap {\npublic:\n  \/\/ Return the min element.\n  int peek() const { return data_[0]; }\n\n  \/\/ Extract the min element.\n  int pop() {\n    \/\/ Swap the min element with the last one. O(1)\n    swap(data_.back(), data_[0]);\n    \/\/ Get the min element. O(1)\n    int min_el = data_.back();\n    \/\/ Evict the min element. O(1)\n    data_.pop_back();\n    \/\/ Maintain heap property. \u03b8(logn)\n    heapifyDown(0);\n    return min_el;\n  }\n\n  \/\/ Add a new element to the heap.\n  void push(int key) {\n    \/\/ Add the element to the end of the array. O(1)\n    data_.push_back(key);\n    \/\/ Maintain heap property. \u03b8(logn)\n    heapifyUp(data_.size() - 1);\n  }\n\n  \/\/ Return the size of the heap.\n  int size() const { return data_.size(); }\nprivate:\n  void heapifyUp(int index) {\n    \/\/ Stop at root.\n    if (index == 0) return;\n    int parent = (index - 1) \/ 2;\n    \/\/ Stop if greater or euqal to parent.\n    if (data_[index] >= data_[parent]) return;\n    \/\/ Swap with parent.\n    swap(data_[index], data_[parent]);\n    \/\/ Continue heapifyUp on parent.\n    heapifyUp(parent);\n  }\n\n  void heapifyDown(int index) {\n    int left = index * 2 + 1;\n    int right = index * 2 + 2;\n    \/\/ Stop if has no left child.\n    if (left >= data_.size()) return;\n    \/\/ Get the min child.\n    int min_child = \n      right < data_.size() &#038;&#038; data_[right] < data_[left] ? right : left;\n    \/\/ Stop if less or euqal to min child.\n    if (data_[index] <= data_[min_child])\n      return;\n    \/\/ Swap with min child.\n    swap(data_[index], data_[min_child]);\n    \/\/ Continue heapifyDown on min_child.\n    heapifyDown(min_child);\n  }\n\n  vector<int> data_;\n};\n\nint main() {\n  vector<int> data{5,1,3,5,3,4,3,7};\n  MinHeap heap;\n  for (int x : data)\n    heap.push(x);\n  vector<int> output;\n  while (heap.size())\n    output.push_back(heap.pop());\n  assert(output == vector<int>({1,3,3,3,4,5,5,7}));\n}\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python3<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nclass MinHeap:\n  def __init__(self, data = None):\n    self.data = list(data) if data else []\n    for i in range((len(self.data)) \/\/ 2, -1, -1):\n      self.heapifyDown(i)\n\n  def push(self, key):\n    self.data.append(key)\n    self.heapifyUp(len(self.data) - 1)\n \n  def pop(self):\n    self.swap(0, -1)\n    min_el = self.data.pop()\n    self.heapifyDown(0)\n    return min_el\n \n  def size(self):\n    return len(self.data)\n \n  def swap(self, i, j):\n    self.data[i], self.data[j] = self.data[j], self.data[i]\n \n  def heapifyDown(self, i):\n    smallest = i\n    for c in [2 * i + 1, 2 * i + 2]:\n      if c < self.size() and self.data[c] < self.data[smallest]: smallest = c\n    if smallest != i:\n      self.swap(i, smallest)\n      self.heapifyDown(smallest)\n \n  def heapifyUp(self, i):\n    if i == 0: return\n    parent = (i - 1) \/\/ 2\n    if self.data[i] >= self.data[parent]: return\n    self.swap(i, parent)\n    self.heapifyUp(parent)\n\ndef test():\n  data = [5,1,3,5,3,4,3,7]\n  heap = MinHeap()\n  for x in data: heap.push(x)\n  output = []\n  while heap.size():\n    output.append(heap.pop())\n  assert output == sorted(data)\n\ndef testBuildHeap():\n  data = [5,1,3,5,3,4,3,7]\n  heap = MinHeap(data)\n  output = []\n  while heap.size():\n    output.append(heap.pop())\n  assert output == sorted(data)\n\ndef main():\n  test()\n  testBuildHeap()\n \nif __name__ == '__main__':\n  main()\n\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>\/\/ Author: Huahua #include #include #include using namespace std; class MinHeap { public: \/\/ Return the min element. int peek() const { return data_[0]; }&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[170],"tags":[],"class_list":["post-7678","post","type-post","status-publish","format-standard","hentry","category-sp","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7678","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7678"}],"version-history":[{"count":7,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7678\/revisions"}],"predecessor-version":[{"id":7694,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7678\/revisions\/7694"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7678"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7678"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7678"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}