We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Now I think I get it. The reason we swap is to preserve the heap property all over the tree. When a new element is added, it may be the current smallest one. You do it by looking at every element of the heap and it is O(N) time. My solution does it in O(logN). I only walk on a branch from leaf up until to the root.
QHEAP1
You are viewing a single comment's thread. Return to all comments →
Now I think I get it. The reason we swap is to preserve the heap property all over the tree. When a new element is added, it may be the current smallest one. You do it by looking at every element of the heap and it is O(N) time. My solution does it in O(logN). I only walk on a branch from leaf up until to the root.