Join Raghavendra Dixit for an in-depth discussion in this video Deleting the root, part of Introduction to Data Structures & Algorithms in Java.
- [Instructor] Another common operation that we do in heaps is to delete the root element. This would usually be done in context of using the heap as priority queues, alright? So in this example, if you delete the root node, which node should become the root now? Of course, keeping the heap properties intact. Well, what we can do is that we first bring the last node in the heap to the place of the root, and then fix the heap by pushing it down so that it maintains the second heap property as well.
So here 10 is smaller than both 15 and 12, so we exchange it with the larger node, which is 15. Then 10 is smaller than both 13 and 11, so we exchange it with 13, which is greater of the 13 and 11. And now the heap is fixed. So essentially, after moving the last node to the root, we keep checking if this node is smaller than its two children and if it is, we exchange it with the larger of the two children, alright? Now, what is the time complexity of deleting the root? Well, we have a constant number of steps in putting the last node as the new root because we will need to update a few references, right? And then for fixing the heap, the number of steps will be proportional to log n because in the worst case, the node may have to travel from the root to the last level of the heap.
So overall, it takes order of log n time to delete the root node of the heap.
Note: This course was created by Packt Publishing. We are pleased to host this training in our library.
- Why study data structures and algorithms?
- How to calculate the time complexity
- Using Big O notation
- Using basic sorting and search algorithms
- Searching elements in unordered arrays and ordered arrays
- Implementing a linked list in Java
- Implementing stacks using arrays
- Queues using arrays
- Binary search trees
- Representing heaps using arrays
Skill Level Intermediate
1. Introduction to Algorithms
2. Analysis of Algorithms
3. Basic Sorting and Search Algorithms
4. Linked Lists
5. Stacks and Queues
7. Binary Search Trees
8. More Sorting Algorithms
- Mark as unwatched
- Mark all as unwatched
Are you sure you want to mark all the videos in this course as unwatched?
This will not affect your course history, your reports, or your certificates of completion for this course.Cancel
Take notes with your new membership!
Type in the entry box, then click Enter to save your note.
1:30Press on any video thumbnail to jump immediately to the timecode shown.
Notes are saved with you account but can also be exported as plain text, MS Word, PDF, Google Doc, or Evernote.