C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
// Author: Huahua #include <assert.h> #include <iostream> #include <vector> using namespace std; class MinHeap { public: // Return the min element. int peek() const { return data_[0]; } // Extract the min element. int pop() { // Swap the min element with the last one. O(1) swap(data_.back(), data_[0]); // Get the min element. O(1) int min_el = data_.back(); // Evict the min element. O(1) data_.pop_back(); // Maintain heap property. θ(logn) heapifyDown(0); return min_el; } // Add a new element to the heap. void push(int key) { // Add the element to the end of the array. O(1) data_.push_back(key); // Maintain heap property. θ(logn) heapifyUp(data_.size() - 1); } // Return the size of the heap. int size() const { return data_.size(); } private: void heapifyUp(int index) { // Stop at root. if (index == 0) return; int parent = (index - 1) / 2; // Stop if greater or euqal to parent. if (data_[index] >= data_[parent]) return; // Swap with parent. swap(data_[index], data_[parent]); // Continue heapifyUp on parent. heapifyUp(parent); } void heapifyDown(int index) { int left = index * 2 + 1; int right = index * 2 + 2; // Stop if has no left child. if (left >= data_.size()) return; // Get the min child. int min_child = right < data_.size() && data_[right] < data_[left] ? right : left; // Stop if less or euqal to min child. if (data_[index] <= data_[min_child]) return; // Swap with min child. swap(data_[index], data_[min_child]); // Continue heapifyDown on min_child. heapifyDown(min_child); } vector<int> data_; }; int main() { vector<int> data{5,1,3,5,3,4,3,7}; MinHeap heap; for (int x : data) heap.push(x); vector<int> output; while (heap.size()) output.push_back(heap.pop()); assert(output == vector<int>({1,3,3,3,4,5,5,7})); } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
# Author: Huahua class MinHeap: def __init__(self, data = None): self.data = list(data) if data else [] for i in range((len(self.data)) // 2, -1, -1): self.heapifyDown(i) def push(self, key): self.data.append(key) self.heapifyUp(len(self.data) - 1) def pop(self): self.swap(0, -1) min_el = self.data.pop() self.heapifyDown(0) return min_el def size(self): return len(self.data) def swap(self, i, j): self.data[i], self.data[j] = self.data[j], self.data[i] def heapifyDown(self, i): smallest = i for c in [2 * i + 1, 2 * i + 2]: if c < self.size() and self.data[c] < self.data[smallest]: smallest = c if smallest != i: self.swap(i, smallest) self.heapifyDown(smallest) def heapifyUp(self, i): if i == 0: return parent = (i - 1) // 2 if self.data[i] >= self.data[parent]: return self.swap(i, parent) self.heapifyUp(parent) def test(): data = [5,1,3,5,3,4,3,7] heap = MinHeap() for x in data: heap.push(x) output = [] while heap.size(): output.append(heap.pop()) assert output == sorted(data) def testBuildHeap(): data = [5,1,3,5,3,4,3,7] heap = MinHeap(data) output = [] while heap.size(): output.append(heap.pop()) assert output == sorted(data) def main(): test() testBuildHeap() if __name__ == '__main__': main() |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment