The Heap as an Abstract Data Type (ADT) is:
A binary tree with the following attributes:
- It is complete that is each level of the tree is completely filled , except possibly the bottom
level and in this level , the nodes are in the left most position.
- It satisfies the heap-order property :
“The data item stored in each node >= the data items stored in its children”
------------------------------------------------------------------
Variants:-
=========
1. Binary heap
2. Binomial heap
3. D-ary heap
4. Fibonacci heap
5. Pairing heap
6. Leftist heap
7. Soft heap
8. 2-3 heap
------------------------------------------------------------------
..When we implement the heap we should do the following:-
==============================================
1. We simply number the nodes in the heap from top to bottom (Numbering the nodes
in each level from left to right )
2. Store the data in the ith node in the ith location of the array (because the heap will
serve as the basis for sorting method , we will not store a list element in location 0 of
the array for the consistency with the other sorting algorithms)
3. The completeness property of the heap guarantees that these data items will be
stored in consecutive locations at the beginning of the array.
-----------------------------------------------------------------
Basic Operations of the heap:-
==========================
1. Construct an empty heap:-
-set mySize equal to 0
-allocating the array if we use dynamic array
2. Check if the heap is empty:- check if mySize = 0 or not.
3. Retrieve the largest element (Max element):-
-return the root of my binary tree which is stored in MyArray [1]
4. Inserting an item:-
To insert an item in a heap we should make the percolate-up operation .
If we want to insert 50 into the following heap :
We will do the following :
A.
B. Then percolate it up the tree by inter changing it with its parent so long as it is greater than its parent
----------------------------------------------------------------------
Percolating _ Up :-
==================
.. To add an element to a heap we,
• put the element at the end of the lowest level and
• percolate up.
.. Percolating up is fairly simple
• At each step, we compare the percolated node to its parent.
• If the percolated node is smaller (violating the heap property), we swap the two and
continue up the tree.
• Otherwise, we're done, since the heap property is no longer violated.
.. When we do the swap,
• the subtree that contains the old parent is clearly in heap order (the old parent was an
ancestor to all the nodes in that subtree, and therefore smaller) and
• the present node is clearly smaller than both of its new subtrees (it's smaller than the
old parent, and the old parent was smaller than everything else below it ).
.. Eventually, we stop (either because we no longer violate heap property or because we reach
the root).
An algorithm for percolate_up:-
============================
/*MyArray [1],….,MyArray [mySize] stores a heap and an item is to be added to the
array so that the result is still a heap*/
1. Increment mySize //add item at end of the tree
2. Set MyArray [mySize] = item
3. Set loc=mySize and parent = (loc -1)/2
4. While parent-1 & MyArray [loc] > MyArray [parent]
Do the following
a. Interchange MyArray [loc] & MyArray [parent]
b. Set loc = parent & parent = (loc - 1)/2
End while
-----------------------------------------------------------------
5. Remove the largest element:-
to remove the max element from the preceding heap consider the following:
A. The max element is at the root , and we remove it by replacing it with the last node
in the tree & decrementing mySize by 1.
the resulting tree is called semiheap because:-
. It is complete
. Both subtrees are heaps
B.We must convert the semiheap into a heap by interchanging the root with the larger
of its 2 children.
C. The new root is greater than its children but the left subtree isn’t a heap so we will
do “percolate down” to this subtree as follows:
------------------------------------------------------------------------------------
Percolating _ down:-
==================
.. Percolating an element down is slightly more difficult than percolating up, since there are
two possible subtrees to move to. As you might guess, you must swap with the root of the
smaller subtree and then continue within that subtree.
..Why don't we worry about increasing the size of the wrong subtree? (As we did in building
binary search trees.) Because we're not changing the size of the subtrees. We're swapping
elements, but not adding them.
.. In some sense, deletion reverses the process of insertion (delete last element in the heap vs.
insert last element in heap; percolate down vs. percolate up).
An algorithm for percolate_down :-
============================
/*[MyArray [r],……,MyArray [n]] stores a semiheap-only the value in heap [r] may
fail the heap-order condition . This semiheap is to be converted into a heap*/
1. Set c=2*r //c is location of the left child
2. While r - n do the following :-
a. If c < style="color: rgb(0, 153, 0);">//if r has 2 children &
MyArray [c] < style="color: rgb(0, 153, 0);">//right child is the larger
Increment c by 1 //make the c the right child
// swap node and the largest child if necessary , and
// move down to the next subtree
b. If MyArray [r] < style="color: rgb(0, 153, 0);"> //order cond. Fails at the parent
i. swap MyArray [r] & My Array [c]
ii.set r=c
iii.set c=2*c
else //heap-order cond. holds
terminate the repetition
End while
---------------------------------------------------------------------------
2. A heap (or maxheap) organizes the list elements in such a way that insertions and removal of the largest (or the smallest for a minheap) element can be done in O(log 2 n) time.
3. The heap is one of the most efficient implementations of the priority queue.
4. Heap applications : -Heapsort : one of the best sorting methods -Selection algorithm : finding the min , max or both of them -Graph algorithms
5. Heaps are a particular form of binary tree designed to provide quick access to the highest-priority element in the tree.
6. Heaps must be balanced (it's part of the definition).
7. In particular, a heap is
o a binary tree,
o that is nearly complete in that:-
- at most one node has one child (the rest have zero or two)
- the nodes on the last level are at the left-hand-side of the level (that is, if a
node has one or two children, all of its left siblings have two children)
o and that has the heap property: the value stored in each node is of higher priority
(lower value) than the values stored below it.
8. The difference between the heaps & stacks :-
o When you create an object in the stack, the object will be deleted at end of the
scope.
o When you create an object in the heap, it is in memory and will be only deleted
when you call the delete function.
9. The height of an n-element heap based on a binary tree is log n .
I hope I can help .. we inshaaAllah hanazel el code soon .. here is the pdf version Heaps
References :- Wikipedia(http://en.wikipedia.org/wiki/Heap_(data_structure)), Data structure & problem solving with C++ "Larry Nyhoff",CIS Department Tutorial
------------------------------------------------------------------
Variants:-
=========
1. Binary heap
2. Binomial heap
3. D-ary heap
4. Fibonacci heap
5. Pairing heap
6. Leftist heap
7. Soft heap
8. 2-3 heap
------------------------------------------------------------------
..When we implement the heap we should do the following:-
==============================================
1. We simply number the nodes in the heap from top to bottom (Numbering the nodes
in each level from left to right )
2. Store the data in the ith node in the ith location of the array (because the heap will
serve as the basis for sorting method , we will not store a list element in location 0 of
the array for the consistency with the other sorting algorithms)
3. The completeness property of the heap guarantees that these data items will be
stored in consecutive locations at the beginning of the array.
-----------------------------------------------------------------
Basic Operations of the heap:-
==========================
1. Construct an empty heap:-
-set mySize equal to 0
-allocating the array if we use dynamic array
2. Check if the heap is empty:- check if mySize = 0 or not.
3. Retrieve the largest element (Max element):-
-return the root of my binary tree which is stored in MyArray [1]
4. Inserting an item:-
To insert an item in a heap we should make the percolate-up operation .
If we want to insert 50 into the following heap :
We will do the following :
A.
B. Then percolate it up the tree by inter changing it with its parent so long as it is greater than its parent
----------------------------------------------------------------------
Percolating _ Up :-
==================
.. To add an element to a heap we,
• put the element at the end of the lowest level and
• percolate up.
.. Percolating up is fairly simple
• At each step, we compare the percolated node to its parent.
• If the percolated node is smaller (violating the heap property), we swap the two and
continue up the tree.
• Otherwise, we're done, since the heap property is no longer violated.
.. When we do the swap,
• the subtree that contains the old parent is clearly in heap order (the old parent was an
ancestor to all the nodes in that subtree, and therefore smaller) and
• the present node is clearly smaller than both of its new subtrees (it's smaller than the
old parent, and the old parent was smaller than everything else below it ).
.. Eventually, we stop (either because we no longer violate heap property or because we reach
the root).
An algorithm for percolate_up:-
============================
/*MyArray [1],….,MyArray [mySize] stores a heap and an item is to be added to the
array so that the result is still a heap*/
1. Increment mySize //add item at end of the tree
2. Set MyArray [mySize] = item
3. Set loc=mySize and parent = (loc -1)/2
4. While parent-1 & MyArray [loc] > MyArray [parent]
Do the following
a. Interchange MyArray [loc] & MyArray [parent]
b. Set loc = parent & parent = (loc - 1)/2
End while
-----------------------------------------------------------------
5. Remove the largest element:-
to remove the max element from the preceding heap consider the following:
A. The max element is at the root , and we remove it by replacing it with the last node
in the tree & decrementing mySize by 1.
the resulting tree is called semiheap because:-
. It is complete
. Both subtrees are heaps
B.We must convert the semiheap into a heap by interchanging the root with the larger
of its 2 children.
C. The new root is greater than its children but the left subtree isn’t a heap so we will
do “percolate down” to this subtree as follows:
------------------------------------------------------------------------------------
Percolating _ down:-
==================
.. Percolating an element down is slightly more difficult than percolating up, since there are
two possible subtrees to move to. As you might guess, you must swap with the root of the
smaller subtree and then continue within that subtree.
..Why don't we worry about increasing the size of the wrong subtree? (As we did in building
binary search trees.) Because we're not changing the size of the subtrees. We're swapping
elements, but not adding them.
.. In some sense, deletion reverses the process of insertion (delete last element in the heap vs.
insert last element in heap; percolate down vs. percolate up).
An algorithm for percolate_down :-
============================
/*[MyArray [r],……,MyArray [n]] stores a semiheap-only the value in heap [r] may
fail the heap-order condition . This semiheap is to be converted into a heap*/
1. Set c=2*r //c is location of the left child
2. While r - n do the following :-
a. If c < style="color: rgb(0, 153, 0);">//if r has 2 children &
MyArray [c] < style="color: rgb(0, 153, 0);">//right child is the larger
Increment c by 1 //make the c the right child
// swap node and the largest child if necessary , and
// move down to the next subtree
b. If MyArray [r] < style="color: rgb(0, 153, 0);"> //order cond. Fails at the parent
i. swap MyArray [r] & My Array [c]
ii.set r=c
iii.set c=2*c
else //heap-order cond. holds
terminate the repetition
End while
---------------------------------------------------------------------------
Notes
1. In an array based implementation , it is easy to find the children of a given node: The children of the ith node are at locations 2*i &2*i+1 Similarly , the parent of the ith node is easily seen to be in location i/22. A heap (or maxheap) organizes the list elements in such a way that insertions and removal of the largest (or the smallest for a minheap) element can be done in O(log 2 n) time.
3. The heap is one of the most efficient implementations of the priority queue.
4. Heap applications : -Heapsort : one of the best sorting methods -Selection algorithm : finding the min , max or both of them -Graph algorithms
5. Heaps are a particular form of binary tree designed to provide quick access to the highest-priority element in the tree.
6. Heaps must be balanced (it's part of the definition).
7. In particular, a heap is
o a binary tree,
o that is nearly complete in that:-
- at most one node has one child (the rest have zero or two)
- the nodes on the last level are at the left-hand-side of the level (that is, if a
node has one or two children, all of its left siblings have two children)
o and that has the heap property: the value stored in each node is of higher priority
(lower value) than the values stored below it.
8. The difference between the heaps & stacks :-
o When you create an object in the stack, the object will be deleted at end of the
scope.
o When you create an object in the heap, it is in memory and will be only deleted
when you call the delete function.
9. The height of an n-element heap based on a binary tree is log n .
I hope I can help .. we inshaaAllah hanazel el code soon .. here is the pdf version Heaps
References :- Wikipedia(http://en.wikipedia.org/wiki/Heap_(data_structure)), Data structure & problem solving with C++ "Larry Nyhoff",CIS Department Tutorial