How do I find the median of numbers in linear time using heaps?

by

You would use a min-max-median heap to find the min, max and median in constant time (and take linear time to build the heap). You can use order-statistics trees to find the kth smallest/largest value. Both of these data structures are described in this paper on min-max heaps [PDF]. Min-max heaps are binary heaps that alternate between min-heaps and max-heaps.

From the paper:

A min-max-median heap is a binary tree with the following properties:

  1. The median of all elements is located at the root

  2. The left subtree of the root is a min-max heap Hl of size ceiling[((n-1)/2)] containing elements less than or equal to the median. The right subtree is a max-min heap Hr of size floor[((n-1)/2)] containing only elements greater than or equal to the median.

The paper goes on to explain how to build such a heap.

Upon reading the paper more thoroughly it appears as though building the min-max-median heaps requires that you first find the median (FTA: “Find the median of all n elements using any one of the known linear-time algorithms”). That said, once you have built the heap you can maintain the median simply by maintaining the balance between the min-max heap on the left and the max-min heap on the right. DeleteMedian replaces the root with either the min of the max-min heap or the max of the min-max heap (whichever maintains the balance).

So if you plan on using a min-max-median heap to find the median of a fixed data set you’re SOL but if you are using it on a changing data set it is possible.

More Related Contents:

  1. Find running median from a stream of integers
  2. Finding the median of an unsorted array
  3. Argument for O(1) average-case complexity of heap insertion
  4. O(klogk) time algorithm to find kth smallest element from a binary heap
  5. What is a plain English explanation of “Big O” notation?
  6. How can I find the time complexity of an algorithm?
  7. What does O(log n) mean exactly?
  8. Difference between Big-O and Little-O Notation
  9. How can building a heap be O(n) time complexity?
  10. Is there an O(n) integer sorting algorithm?
  11. Hash table runtime complexity (insert, search and delete)
  12. Heap vs Binary Search Tree (BST)
  13. Time complexity of Euclid’s Algorithm
  14. What would cause an algorithm to have O(log log n) complexity?
  15. how to calculate binary search complexity
  16. Time complexity of Sieve of Eratosthenes algorithm
  17. How to delete in a heap data structure?
  18. “On-line” (iterator) algorithms for estimating statistical median, mode, skewness, kurtosis?
  19. Are there any cases where you would prefer a higher big-O time complexity algorithm over the lower one?
  20. Sorting in linear time? [closed]
  21. How to calculate or approximate the median of a list without storing the list
  22. O(n) algorithm to find the median of n² implicit numbers
  23. Examples of Algorithms which has O(1), O(n log n) and O(log n) complexities
  24. Why do we ignore co-efficients in Big O notation?
  25. What is the time complexity of heapq.nlargest?
  26. Print the biggest K elements in a given heap in O(K*log(K))?
  27. Algorithm for merging two max heaps?
  28. Do iterative and recursive versions of an algorithm have the same time complexity?
  29. Computational complexity of base conversion
  30. Merge sort time and space complexity

Leave a Comment