Leetcode 295 is to find median in a data stream.
I want to use two heaps to implement it. which can make add a data from stream in O(logn), get the percentile in O(1).
left_heap is a min_heap which used to save the left data of requied percentile.
right_heap used to save data which is larger than percentile.
In class SortedStream, which can make add data o(logn) and make findMedian o(1)
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
class SortedStream {
public:
SortedStream(double percent, size_t rsize = 65536*16) : percent_(percent), reserve_size_(rsize) {
init();
}
void push(double v) { // time complexity, o(logn)
size_;
double left_top = left_data_.back();
if (left_data_.empty() || v <= left_top) { left_data_.push_back(v); std::push_heap(left_data_.begin(), left_data_.end(), std::less<double>{}); }
else { right_data_.push_back(v); std::push_heap(right_data_.begin(), right_data_.end(), std::greater<double>{}); }
size_t idx = size_ * percent_ 1;
size_t left_size = left_data_.size();
if (idx < left_size) {
// pop left top into right
std::pop_heap(left_data_.begin(), left_data_.end(), std::less<double>{});
double left_top = left_data_.back();
left_data_.pop_back();
right_data_.push_back(left_top);
std::push_heap(right_data_.begin(), right_data_.end(), std::less<double>{});
} else if (idx > left_size) {
// pop right top into left
std::pop_heap(right_data_.begin(), right_data_.end(), std::greater<double>{});
double right_top = right_data_.back();
right_data_.pop_back();
left_data_.push_back(right_top);
std::push_heap(left_data_.begin(), left_data_.end(), std::greater<double>{});
}
}
void init() {
size_t lsize = reserve_size_ * percent_ 2;
left_data_.reserve(lsize);
right_data_.reserve(reserve_size_ - lsize 2);
max_ = INT_MIN;
min_ = INT_MAX;
std::make_heap(left_data_.begin(), left_data_.end(), std::less<double>{});
std::make_heap(right_data_.begin(), right_data_.end(), std::greater<double>{});
size_ = 0;
}
size_t size() const { return size_; }
double max() const { return max_; }
double min() const { return min_; }
double percentile() const { // time complexity o(1)
return left_data_.back();
}
public:
double percent_;
size_t size_;
double max_, min_;
std::vector<double> left_data_, right_data_;
size_t reserve_size_;
};
class MedianFinder {
public:
MedianFinder() : ss(0.5){}
void addNum(int num) {ss.push(num);}
double findMedian() {return ss.percentile();}
SortedStream ss;
};
int main() {
MedianFinder* obj = new MedianFinder();
for (size_t i = 0; i< 15; i) {
obj->addNum(i);
double param_2 = obj->findMedian();
cout << "i = " << i << " median = " << param_2 << endl;
}
}
it's ok to run in my laptop, but when i submit in leetcode, it comes out:
Line 863: Char 45: runtime error: applying non-zero offset 18446744073709551608 to null pointer (stl_iterator.h)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c /9/bits/stl_iterator.h:868:45
I never see this error. can you help on this?
CodePudding user response：
You have one minor problem
In the line
double left_top = left_data_.back();
At the very beginning, the std::vector "left_data" will be empty. If you try to access the last element of an empty vector, you will get an runtime error.
If you modify this line to for example:
double left_top = left_data_.empty()?0.0:left_data_.back();
Then your program will work as you expect it to work.
I personally find the approach a a little bit too complicated. Maybe you could use a std::multiset or a std::priority_queue. Especially the std::priority_queue will also implement a max-heap and a min-hep for you, without out the overhead of calling std::vectors heap functions.
But I am still in favor of the std::multiset . . .
CodePudding user response：
I like your (OP's) idea that Heap can be used to solve the task, heap of smaller and larger values. Also as @ArminMontigny suggested one can use std::priority_queue instead of plain heap, because priority queue is based on heap and adds easy to use helper methods. Regular heap is a kind of low-level backend for priority queue.
Based on these two suggestions and inspired by your interesting question I decide to implement short (30 lines) solution for your task (it uses random numbers as example input):
#include <queue>
#include <random>
#include <iostream>
int main() {
std::mt19937_64 rng{123};
std::priority_queue<int> smaller;
std::priority_queue<int, std::vector<int>, std::greater<int>> larger;
for (size_t i = 0; i < 100; i) {
int n = rng() % 1000;
if (smaller.empty() || n <= smaller.top())
smaller.push(n);
else
larger.push(n);
while (smaller.size() 1 < larger.size()) {
smaller.push(larger.top());
larger.pop();
}
while (larger.size() 1 < smaller.size()) {
larger.push(smaller.top());
smaller.pop();
}
double median = smaller.size() == larger.size() ?
(smaller.top() larger.top()) / 2.0 :
smaller.size() < larger.size() ? larger.top() : smaller.top();
std::cout << "n = " << n << " med = " << median << " | ";
if ((i 1) % 4 == 0)
std::cout << std::endl;
}
}
Output:
n = 504 med = 504 | n = 771 med = 637.5 | n = 101 med = 504 | n = 790 med = 637.5 |
n = 380 med = 504 | n = 388 med = 446 | n = 888 med = 504 | n = 406 med = 455 |
n = 53 med = 406 | n = 240 med = 397 | n = 749 med = 406 | n = 438 med = 422 |
n = 566 med = 438 | n = 238 med = 422 | n = 741 med = 438 | n = 817 med = 471 |
n = 810 med = 504 | n = 376 med = 471 | n = 816 med = 504 | n = 503 med = 503.5 |
n = 599 med = 504 | n = 264 med = 503.5 | n = 704 med = 504 | n = 132 med = 503.5 |
n = 740 med = 504 | n = 391 med = 503.5 | n = 563 med = 504 | n = 778 med = 533.5 |
n = 768 med = 563 | n = 136 med = 533.5 | n = 964 med = 563 | n = 368 med = 533.5 |
n = 653 med = 563 | n = 941 med = 564.5 | n = 976 med = 566 | n = 680 med = 582.5 |
n = 546 med = 566 | n = 200 med = 564.5 | n = 387 med = 563 | n = 698 med = 564.5 |
n = 562 med = 563 | n = 251 med = 562.5 | n = 257 med = 562 | n = 735 med = 562.5 |
n = 822 med = 563 | n = 212 med = 562.5 | n = 576 med = 563 | n = 368 med = 562.5 |
n = 783 med = 563 | n = 964 med = 564.5 | n = 234 med = 563 | n = 805 med = 564.5 |
n = 952 med = 566 | n = 162 med = 564.5 | n = 936 med = 566 | n = 493 med = 564.5 |
n = 88 med = 563 | n = 313 med = 562.5 | n = 580 med = 563 | n = 274 med = 562.5 |
n = 353 med = 562 | n = 701 med = 562.5 | n = 882 med = 563 | n = 249 med = 562.5 |
n = 19 med = 562 | n = 482 med = 554 | n = 327 med = 546 | n = 402 med = 525 |
n = 379 med = 504 | n = 521 med = 512.5 | n = 977 med = 521 | n = 550 med = 533.5 |
n = 434 med = 521 | n = 82 med = 512.5 | n = 581 med = 521 | n = 134 med = 512.5 |
n = 532 med = 521 | n = 860 med = 526.5 | n = 562 med = 532 | n = 225 med = 526.5 |
n = 907 med = 532 | n = 837 med = 539 | n = 671 med = 546 | n = 785 med = 548 |
n = 593 med = 550 | n = 533 med = 548 | n = 471 med = 546 | n = 352 med = 539.5 |
n = 388 med = 533 | n = 532 med = 532.5 | n = 310 med = 532 | n = 135 med = 532 |
n = 323 med = 532 | n = 81 med = 526.5 | n = 849 med = 532 | n = 577 med = 532 |
n = 643 med = 532 | n = 956 med = 532.5 | n = 204 med = 532 | n = 383 med = 532 |
Regarding your question about Sanitizer error - this sanitizer is a part of CLang. You can download Clang yourself and try it out on your home laptop, to reproduce exactly same error.
To get same error add option -fsanitize=undefined, when compiling using CLang at home.
For Windows CLang can be downloaded from this page. Also on Windows if you have great package manager Chocolatey, then you can install CLang LLVM through short command choco install llvm.
For Linux CLang can be installed through sudo apt install clang.
Also you can use great online website GodBolt, by this link, at given link I already chosen CLang for compilation and put necessary options -std=c 11 -O0 -fsanitize=undefined, so you have just to start coding in the window to the left-handside when you open the link.