How Do You Add or Remove Elements from Heaps and Binary Trees?

In summary, the conversation discusses the difficulty of understanding how to add/remove from heaps and binary trees and asks for recommendations on visualizing these operations. The response provides a summary of how to delete from a binary search tree in three different cases: when the node has one child, no children, or two children. It recommends using Robert Sedgewick's book "Algorithms" for understanding heap structures and operations.
  • #1
n00neimp0rtnt
15
0
I have been given a practice exam from my professor (http://www.cs.pitt.edu/~aronis/cs0445/miscellaneous/cs445-spring-2007-test-3.pdf ) along with an answer sheet (http://www.cs.pitt.edu/~aronis/cs0445/miscellaneous/cs445-spring-2007-test-3-answers.txt ) and there are a good number of questions on heaps and binary trees. Unfortunately, he's a pretty bad professor and never exactly "showed us" how to add/remove to/from a heap or a binary tree. I'm looking for a good "visualization" of how to do this, and googling hasn't gotten me very far. If anyone has a web page or even notes from your own class on adding and removing from these data structures, it would be greatly appreciated.

Thanks!
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
In "Algorithms", Robert Sedgewick uses around 10 pages to describe and visualize the heap structure and operations. I would recommend that book (or one of his language specific editions) for any CS book shelf.
 
  • #3
deleting from a binary search tree:

case 1: the node you want to delete ( the node with 7 ) has 1 child:

Code: 
   6
5    7 
        8

solution: disconnect it from the tree by directly linking 7's only child to the node above

Code: 
   6
5     8
case 2: the node you want to delete has no children (say, 7 again)

Code: 
   6
5     7
solution: this case is trivial, just delete it off

Code: 
   6
5
case 3: the node you want to delete has 2 children (7 again):

Code: 
     5
        7 
     6     8
solution: Find its successor node (next node in a sorted order), copy it up to 7's position

Code: 
     5
        8 
     6     8
now delete 8 from the subtree mainroot.right.right with one of the cases above

final:

Code: 
     5
        8 
     6
notice how in the 2 children case (case 3), when deleting the successor node from the respective subtree, you will always end up doing case 1 or 2 again (the "easy" cases)
 

1. What is a heap in computer science?

A heap is a specialized tree-based data structure that is used to efficiently store and retrieve data with a specific ordering. It is commonly used to implement priority queues, which are data structures that allow for efficient retrieval of the "maximum" or "minimum" element in the data set.

2. What is the difference between a binary tree and a heap?

A binary tree is a data structure where each node has at most two child nodes. On the other hand, a heap is a type of binary tree that follows a specific ordering property. In a max heap, the value of a parent node is always greater than or equal to the values of its child nodes. In a min heap, the value of a parent node is always smaller than or equal to the values of its child nodes.

3. How do you insert elements into a heap?

To insert an element into a heap, you first add it to the bottom level of the heap at the leftmost open space. Then, you compare the value of the new element with its parent node and swap them if necessary to maintain the heap's ordering property. This process is repeated until the new element is in its correct position in the heap.

4. What is the time complexity of inserting an element into a heap?

The time complexity of inserting an element into a heap is O(log n), where n is the number of elements in the heap. This is because the insertion process involves comparing the new element with its parent node and potentially swapping it multiple times until it is in its correct position. Since the height of a heap is log n, the time complexity is O(log n).

5. How do you remove the maximum/minimum element from a heap?

To remove the maximum element from a max heap, you swap it with the last element in the heap and then delete the last element. Then, you compare the new root node with its child nodes and swap them if necessary to maintain the heap's ordering property. This process is repeated until the new root is in its correct position. The process for removing the minimum element from a min heap is similar, but you swap the minimum element with the last element and compare it with its child nodes to maintain the ordering property.

Similar threads

TabletPCs for Science and Science Teaching [blog entry from 2006]
    • Computing and Technology
Replies
4
Views
3K
C/C++ What are the new features in C++0x and how do they work?
    • Programming and Computer Science
2
Replies
49
Views
10K
Programs Math minor, double major, and elective classes advice
    • STEM Academic Advising
Replies
4
Views
2K
Mathematica This Week's Finds in Mathematical Physics (Week 257)
    • MATLAB, Maple, Mathematica, LaTeX
Replies
5
Views
3K

Hot Threads

Recent Insights

Back
Top