How to delete in a heap data structure?

by

Actually, you can remove an item from the middle of a heap without trouble.

The idea is to take the last item in the heap and, starting from the current position (i.e. the position that held the item you deleted), sift it up if the new item is greater than the parent of the old item. If it’s not greater than the parent, then sift it down.

That’s the procedure for a max heap. For a min heap, of course, you’d reverse the greater and less cases.

Finding an item in a heap is an O(n) operation, but if you already know where it is in the heap, removing it is O(log n).

I published a heap-based priority queue for DevSource a few years back. The full source is at http://www.mischel.com/pubs/priqueue.zip

Update

Several have asked if it’s possible to move up after moving the last node in the heap to replace the deleted node. Consider this heap:

        1
    6       2
  7   8   3

If you delete the node with value 7, the value 3 replaces it:

        1
    6       2
  3   8

You now have to move it up to make a valid heap:

        1
    3       2
  6   8

The key here is that if the item you’re replacing is in a different subtree than the last item in the heap, it’s possible that the replacement node will be smaller than the parent of the replaced node.

More Related Contents:

  1. O(klogk) time algorithm to find kth smallest element from a binary heap
  2. Algorithm for merging two max heaps?
  3. How to create the most compact mapping n → isprime(n) up to a limit N?
  4. Reverse the ordering of words in a string
  5. Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations
  6. Data structures for loaded dice?
  7. Find kth smallest element in a binary search tree in Optimum way
  8. Find running median from a stream of integers
  9. How to implement a queue using two stacks?
  10. Computing set intersection in linear time?
  11. Array remove duplicate elements
  12. What is the difference between tree depth and height?
  13. Finding the median of an unsorted array
  14. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  15. What is the fastest way to find the closest point to a given point?
  16. Skip List vs. Binary Search Tree
  17. Algorithm for autocomplete?
  18. Hashing a Tree Structure
  19. graph – Dijkstra for The Single-Source Longest Path
  20. Print the biggest K elements in a given heap in O(K*log(K))?
  21. How can I return an array of struct in solidity?
  22. The intersection of all combinations of n sets
  23. Prove that binary heap build max comparsion is (2N-2)
  24. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  25. How do I find the median of numbers in linear time using heaps?
  26. Why are hash table expansions usually done by doubling the size?
  27. What are probabilistic data structures?
  28. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  29. Why is vector array doubled?
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment