###### Asked in Computer ProgrammingDatabase ProgrammingC Programming

Computer Programming

Database Programming

C Programming

# Difference between binary search tree and heap tree?

## Answer

###### Wiki User

###### October 11, 2010 12:08AM

A binary search tree uses the definition: that for every node,the node to the left of it has a less value(key) and the node to the right of it has a greater value(key).

Where as the heap,being an implementation of a binary tree uses the following definition:

If A and B are nodes, where B is the child node of A,then the value(key) of A must be larger than or equal to the value(key) of B.That is,

key(*A*) ≥ key(*B*).

## Related Questions

###### Asked in C Programming, C++ Programming, The Difference Between

### What is the difference between insertion sort and heap sort?

Both insertion sort and heap sort are in-place sorting
techniques( ie they dont require addition memory space). The main
difference between these two techniques is in their efficiency.
Insertion sort has an efficiency of O(n2) while heap sort has an
efficiency of O(n*log n). Hence heap sort is faster.

###### Asked in Definitions

### Definition of heap sort?

###### Asked in C Programming, The Difference Between

### Difference between binomial heap and Fibonacci heap?

Like a binomial heap, a fibonacci heap is a collection of tree.
But in fibonacci heaps, trees are not necessarily a binomial tree.
Also they are rooted, but not ordered.
If neither decrease-key not delete is ever invoked on a
fibonacci heap each tree in the heap is like a binomial heap.
Fibonacci heaps have more relaxed structure than binomial
heaps.

###### Asked in Windows 7, C Programming

### Difference between Fibonacci heap and binomial heap?

Like a binomial heap, a fibonacci heap is a collection of tree.
But in fibonacci heaps, trees are not necessarily a binomial tree.
Also they are rooted, but not ordered.
If neither decrease-key not delete is ever invoked on a
fibonacci heap each tree in the heap is like a binomial heap.
Fibonacci heaps have more relaxed structure than binomial
heaps.

###### Asked in Computer Programming

### What is best algorithm for searching?

It depends on how the data is arranged. In case it is an array,
use linear search or binary search or interpolation search
according as the array is sorted or not and based on the
distribution of data. If some other data structures are used (like
heap) for making data retrieval efficient, other algorithms
exist.

###### Asked in Computer Programming, Database Programming, C Programming, How To

### How to determine an almost complete binary tree is a heap?

A binary heap is defined as follows: # It it an "almost"
complete binary tree. That is, the bottom level of a heap of height
h is partially filled from left to right, and may only have
from 1 to 2h nodes. This may make some of the nodes at level
h-1 into leaf nodes. So a binary heap of height h may
have anywhere from 2h to 2h+1-1 nodes. # It satisfies
the heap property. Each node has some ordered value
associated with it, like a real number. The heap property asserts
that a parent node must be greater than or equal to both of its
children. A binary heap is easily represented using an array, let's
call it A[1..length(A)]. The size of the heap
will be called heap-size(A) (obviously
heap-size(A) <= length(A)). We can
use the first element of the array, element #1, as the root of the
heap. The left child of array element i is at element
2i, and the right child is at element 2i+1. Also, the
parent of an element at node i is at half of i. An
element can tell whether it is a left or right child simply be
checking whether it is even or odd, respectively. We define these
"algorithms" for finding indices parents and children in
pseudocode: Parent (i) return floor (i / 2) Left (i) return 2 * i
Right (i) return 2 * i + 1 You can tell if an array element
i is in the heap simply by checking whether i <=
heap-size(A). Note: this scheme doesn't work
in general with binary (possibly incomplete) trees, since
representing leaf nodes at depths less than the height of the tree
minus 1 isn't possible, and if it were, it would waste space. This
representation of an almost complete binary tree is pretty
efficient, since moving around the tree involves multiplying and
dividing by two, operations that can be done with simple shifts in
logic, and adding one, another simple instruction. Asymptotically
speaking, each of the heap node access functions above consume
O(1) time. ghjghjhjk hjkjk

###### Asked in Computer Programming, PHP Programming, C Programming, C++ Programming

### What is heap sort?

Answer:- A sorting algorithm that works by first organizing the
data to be sorted into a special type of binary tree called a
heap. The heap itself has, by definition, the largest value
at the top of the tree, so the heap sort algorithm must also
reverse the order. It does this with the following steps:
1. Remove the topmost item (the largest) and replace it with the
rightmost leaf. The topmost item is stored in an array.
2. Re-establish the heap.
3. Repeat steps 1 and 2 until there are no more items left in
the heap.
The sorted elements are now stored in an array.
A heap sort is especially efficient for data that is already
stored in a binary tree. In most cases, however, the quick
sort algorithm is more efficient.
GOURAV KHARE (CHANDIGARH)
gouravsonu89@gmail.com

###### Asked in Computer Programming, C Programming, The Difference Between

### What is the difference between stack and heap memory in C?

The stack is a local memory reserve where the program stores
variable and function data. The heap is a special memory reserve
where the programmer can dynamically allocate memory from. The heap
is useful when the programmer doesn't know how large to make
certain variables, he just constructs one of the right size during
run-time.

Load More