0

A type of data structure very common and very used is the Heap. This data structure is characterized by a relationship imposed upon its nodes: if < is a relationship and node is a node, then node < node.child for all the children of the node.

But what happens when you need to change the relationship?

The brute-force way is simply to extract all elements from the Heap and add them to another Heap having the desired relationship: usually that takes O(n log(n)) time. Does it exist a Heap that allow to change its relationship in a faster way, possibly with an in-place algorithm?

Asghabard
  • 191
  • 13
  • You can build a binary heap in-place in an array in O(n) time. So it follows that you can change the relationship and re-order the heap in O(n) time. For an explanation of why that's possible, see https://stackoverflow.com/q/9755721/56778. For a visual example, see https://stackoverflow.com/questions/50947087/build-heap-procedure. For a pseudocode implementation with explanation, see https://stackoverflow.com/questions/47076465/build-a-min-max-heap-in-on-time-complexity. Or just do a Google search on [build heap O(n)]. – Jim Mischel Jan 12 '19 at 03:19
  • This can be done if the Heap is array-based. What about a tree-based heap? – Asghabard Jan 22 '19 at 18:33
  • It works in a tree-based heap, too. The only real difference is that you'll have to do an initial scan of the tree to build a list of nodes to be moved. That takes O(n) time and requires O(n/2) additional space, but it's still going to be faster than O(n log n). – Jim Mischel Jan 22 '19 at 21:57

0 Answers0