gotchaCritical
What's the difference between a binary search tree and a binary heap?
Viewed 0 times
thewhatsearchheapdifferencebetweenbinaryandtree
Problem
These two seem very similar and have almost an identical structure. What's the difference? What are the time complexities for different operations of each?
Solution
Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.
Source: https://stackoverflow.com/a/6147264/781723
Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN) for both structures. If you only care about findMin/findMax (e.g. priority-related), go with heap. If you want everything sorted, go with BST.
Source: https://stackoverflow.com/a/17476698/781723
Source: https://stackoverflow.com/a/6147264/781723
Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN) for both structures. If you only care about findMin/findMax (e.g. priority-related), go with heap. If you want everything sorted, go with BST.
Source: https://stackoverflow.com/a/17476698/781723
Context
StackExchange Computer Science Q#27860, answer score: 94
Revisions (0)
No revisions yet.