手写最大堆-实现
1 class Heap { 2 public: 3 void push(int x){ 4 heap.push_back(x); 5 size += 1; 6 int now = size; 7 while(now!=1) { 8 int parent = now / 2; 9 if(heap[now] > heap[parent]) 10 swap(heap[now], heap[parent]); 11 else break; 12 now = parent; 13 } 14 } 15 16 bool empty(){ 17 return size == 0; 18 } 19 20 int top(){ 21 return heap[1]; 22 } 23 24 int _size(){ 25 return size; 26 } 27 28 int pop(){ 29 int ans = heap[1]; 30 swap(heap[size], heap[1]); 31 heap.pop_back(); 32 size -= 1; 33 int now = 1; 34 while(now * 2 <= size){ 35 int child = now * 2; 36 if(child + 1 <=size && heap[child+1] > heap[child]) 37 child += 1; 38 if(heap[now] < heap[child]) 39 swap(heap[now], heap[child]); 40 else break; 41 now = child; 42 } 43 return ans; 44 } 45 46 private: 47 vector<int> heap = {0}; 48 int size = 0; 49 }; 50 51 52 class Solution { 53 public: 54 vector<int> GetLeastNumbers_Solution(vector<int> input, int k) { 55 Heap h; 56 vector<int> ans; 57 if(k>input.size()) return ans; 58 for(auto it: input) { 59 if(h._size()<k) 60 h.push(it); 61 else{ 62 if(h.top()>it) { 63 h.pop(); 64 h.push(it); 65 } 66 } 67 } 68 while(!h.empty()) ans.push_back(h.pop()); 69 reverse(ans.begin(), ans.end()); 70 return ans; 71 } 72 };