logoalt Hacker News

shihab • yesterday at 6:19 PM • 2 replies • view on HN

I'm curious what you did with the "active sorting range" after a push/pop event. Since it's a vector underneath, I don't see any option other than to sort the entire range after each event, O(N). This would surely destroy performance, right?

Replies

YesBox • yesterday at 9:17 PM

There's no need to resort when popping an item.

When adding an item, it gets added to the next unused vector element. The sorting range end offset gets updated.

Then it sorts (note you would actually need a custom sort since a PriorityQueue is a pair)

  std::push_heap( vec.begin() + startOffset, vec.begin() + endOffset ) [1]
Adding an item would be something like:

  endOffset++; vec.insert( vec.begin() + endOffset, $value );   [1]
Or maybe I just used

  endOffset++; vec[endOffset] = $value;  [1]
Popping an item:

  startOffset++;
[1] Im writing this from memory from my attempt many months ago. May have mistakes.. but should communicate the jist