Hacker News new | ask | show | jobs
by nightcracker 2795 days ago
Ignore all the other noise about expected vs amortized vs just O(1). It's not what's relevant here.

1. Zip trees do not have O(1) insert/remove. They have O(log n) insert/remove (because they have to search the tree to find where to insert/remove), with O(1) additional restructuring time.

2. You can have an ordered data structure with O(1) insert, but not O(1) insert and O(1) find-min simultaneously. You can have O(1) insert trivially by just delaying all actual inserts by putting them into an array, and only actually insert them later when a search happens.