Heap :
A Heap is a binary tree where all the leaves are either present at depth d or d-1 same as complete binary tree.
for every node n, the value in n is greater than or equal to the values in its children, thus also greater or equal
to all of the values in its subtrees.
Conditions for Heap:
1) All leaves are either at depth d or d-1 for same d value
2) All of the leaves at depth d-1 are to the right of the leaves at d depth.
3) There is at most 1 node with just 1 child, that child is the left of its parent and it is the rightmost leaf at depth d.
examples from http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html
A Heap is a binary tree where all the leaves are either present at depth d or d-1 same as complete binary tree.
for every node n, the value in n is greater than or equal to the values in its children, thus also greater or equal
to all of the values in its subtrees.
Conditions for Heap:
1) All leaves are either at depth d or d-1 for same d value
2) All of the leaves at depth d-1 are to the right of the leaves at d depth.
3) There is at most 1 node with just 1 child, that child is the left of its parent and it is the rightmost leaf at depth d.
examples from http://pages.cs.wisc.edu/~vernon/cs367/notes/11.PRIORITY-Q.html
No comments:
Post a Comment