3 ms·

Per the last posts: Number of heaps: O(n^(1/3)). Maximum elements per heap O(n^(2/3)). Lookup of an element. Find the heap with the element (i.e. element betwe

by nikic 11y ago

Per the last posts: Number of heaps: O(n^(1/3)). Maximum elements per heap O(n^(2/3)). Lookup of an element. Find the heap with the element (i.e. element between maximum of previous heap and this heap). Perform linear search in heap. Worst cast complexity O(n^(1/3) + n^(2/3)) = O(n^(2/3)). Insertion of an element. Find the last heap those maximum element is still larger than the element. Extract top element of the heap and insert the new element instead. Then propagate upwards (i.e. extract top of next heap and insert top of previous heap, etc). Worst case is O(n^(1/3) + log(n^(2/3)) * n^(1/3)) = O(log(n) * n^(1/3)). Deletion of an element. Find the heap with the element (i.e. element between maximum of previous heap and this heap). Remove the element from it. Extract top of next heap and insert it into this one. Then continue propagating upwards. So this is O(n^(1/3) + n^(2/3) + log(n^(2/3)) * n^(1/3)) = O(n^(2/3)). Building the structure. Why is this O(n)? If you have already segregated the array into segments for the separate heaps, heapifying them would be O(n). How can the segmentation be done in O(n)? Edit: Using the suggestion of splitting up according to 1+3+5+..+(2n-1) = n^2 we'd get: Search: O(sqrt(n) + sqrt(n)) = O(sqrt(n)) Insert: O(sqrt(n) + log(sqrt(n)) * sqrt(n)) = O(log(n) * sqrt(n) Delete: O(sqrt(n) + sqrt(n) + log(sqrt(n)) * sqrt(n)) = O(log(n) * sqrt(n))

mtdewcmu 11y ago
Deletion can't be done efficiently, as pointed out by Timon Gehr: >> Deletion leaves a hole in one heap, which should be filled by the minimum element of the next heap, etc. The minimum cannot be extracted efficiently from a max-heap.
- azakai 11y ago
  Indeed. If the smallest element is deleted, then we are removing the singleton element of the first heap. We need to find the second-smallest element, which will be in the next heap after it, but it could be any of the leaves. That means we need to traverse O(heapsize) elements. And since we started with the smallest element, this will cascade through each of the heaps, in order to keep them all (but the last) at full size. All together, that's O(N).
- gre 11y ago
  Never used one, but how about a min-max heap instead? https://en.wikipedia.org/wiki/Min-max_heap https://en.wikipedia.org/wiki/Min-max_heap
- nikic 11y ago
  That's true, I got confused with min and max there. gre's suggestion of using a min-max heap (if deletion is required) seems a reasonable workaround for this issue.
  - mtdewcmu 11y ago
    Using min-max heaps should be workable; indeed, the resulting data structure seems to be a special case of the data structure described in section 3 of [1]. [1] http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/...
keeperofdakeys 11y ago
> Building the structure. Why is this O(n)? If you have already segregated the array into segments for the separate heaps, heapifying them would be O(n). How can the segmentation be done in O(n)? Using 1 + 3 + 5 ... = n^2, wouldn't the largest segment hold roughly sqrt(n) elements. So O(sort(n)) heapify for sqrt(n) heaps, or O(sqrt(n) * sqrt(n)) = O(n).

by nikic 11y ago

mtdewcmu 11y ago

Deletion can't be done efficiently, as pointed out by Timon Gehr: >> Deletion leaves a hole in one heap, which should be filled by the minimum element of the next heap, etc. The minimum cannot be extracted efficiently from a max-heap.

azakai 11y ago
Indeed. If the smallest element is deleted, then we are removing the singleton element of the first heap. We need to find the second-smallest element, which will be in the next heap after it, but it could be any of the leaves. That means we need to traverse O(heapsize) elements. And since we started with the smallest element, this will cascade through each of the heaps, in order to keep them all (but the last) at full size. All together, that's O(N).
gre 11y ago
Never used one, but how about a min-max heap instead? https://en.wikipedia.org/wiki/Min-max_heap https://en.wikipedia.org/wiki/Min-max_heap
nikic 11y ago
That's true, I got confused with min and max there. gre's suggestion of using a min-max heap (if deletion is required) seems a reasonable workaround for this issue.
- mtdewcmu 11y ago
  Using min-max heaps should be workable; indeed, the resulting data structure seems to be a special case of the data structure described in section 3 of [1]. [1] http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/MinMaxHeaps.pdf http://www.cs.otago.ac.nz/staffpriv/mike/Papers/MinMaxHeaps/...

keeperofdakeys 11y ago

> Building the structure. Why is this O(n)? If you have already segregated the array into segments for the separate heaps, heapifying them would be O(n). How can the segmentation be done in O(n)? Using 1 + 3 + 5 ... = n^2, wouldn't the largest segment hold roughly sqrt(n) elements. So O(sort(n)) heapify for sqrt(n) heaps, or O(sqrt(n) * sqrt(n)) = O(n).