Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

These two seem very similar and have almost an identical structure. What's the difference? What are the runtime complexities of each?

share|improve this question

4 Answers 4

up vote 6 down vote accepted

With data structure one has to distinguish levels of concern.

One. The abstract data structures (objects stored, their operations) in this question are different. One implements a priority queue, the other a set. A priority queue is not interested in finding a arbitrary element, only the one with largest priority.

Two. The concrete implementation of the structures. Here on first sight both are (binary) trees, with different structural properties though. Both the relative ordering of the keys and the possible global structures differ. As IPlant correctly remarks an heap should be "complete".

Three. There is a final difference in the low level implementation. A (unbalanced) binary search-tree has a standard implementation using pointers. A binary heap to the contrary has an efficient implementation using an array (precisely because of the restricted structure).

share|improve this answer

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.by Dante is not a geek

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.

by xysun

share|improve this answer
    
I think BST is better in findMin & findMax stackoverflow.com/a/27074221/764592 –  Yeo Nov 22 at 5:50

Both binary search trees and binary heaps are both in the set of trees and are tree-based data structures.

Heaps require the nodes to have a priority over their children. In a max heap, each node's children must be less than itself. This is the opposite for a min heap:

Binary Max Heap

Binary search trees (BST) follow a specific ordering (pre-order, in-order, post-order) among sibling nodes. The tree must be sorted, unlike heaps:

Binary Search Tree

BST have average of O(logN) for insertion, deletion, and search.
Binary Heaps have average O(1) for insertion and O(logN) for deletion.

share|improve this answer
3  
Welcome to Computer Science! Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. –  FrankW Jun 20 at 7:17
    
Insertion into binary heaps is $O(\log n)$, not $O(1)$. What is $O(1)$ is extract_min/extract_max. –  FrankW Jun 20 at 7:18

On top of the previous answers, the heap must have the heap structure property; the tree must be full, and the bottom most layer, which cannot always be full, must be filled leftmost to rightmost with no gaps.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.