题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
思路 1：没有排序的数组
由于数据是从数据流中读出来的，因此数据的个数随着时间的增长而增多，我们需要使用一个数据容器去接收来自数据流中的数据。
最直接的思路是：使用不排序的数组作为数据容器。不排序的意思是，每当从数据流中读取一个数据时，直接将这个数据插入数组的尾部，不做任何操作。这样当我们需要计算数组中的中位数时，我们便可以使用 Partition 的思想，找出数组中的中位数。
使用不排序的数组作为数据容器，插入数据的时间复杂度是 O(1)，找出中位数的时间复杂度是 O(n)。
思路 2：排序的数组
这个算法的思路是：使用排序的数组作为数据容器。排序的意思是，每当从数据流中读取一个数据时，插入数组后，数组都要保持排序的状态，也就是说，每次插入数据都需要把比它大的数值往后移动一个位置。在排序完的数组中找出中位数，只需要先判断数组中的元素个数是奇数还是偶数，如果是奇数，那么取出索引为 $\frac{n}{2}$ 的元素即可，否则取出索引为 $\frac{n - 1}{2}$ 和 $\frac{n}{2}$ 的元素加权平均即可。
使用排序的数组作为数据容器，插入数据的时间复杂度是 O(n)，找出中位数的时间复杂度是 O(1)。
思路 3：排序的链表
这个算法的思路是：使用排序的链表作为数据容器。当从数据流中读取一个数据时，从表头遍历到表尾，插入新数据保持链表排序。在插入新数据的同时，定义两个指针，分别指向链表中间的节点，当节点个数为奇数时，两个指针指向同一个节点。
使用排序的链表作为数据容器，插入数据的时间复杂度是 O(n)，找出中位数的时间复杂度是 O(1)。
思路 4：二叉搜索树
这个算法的思路是：使用二叉搜索树作为数据容器。二叉搜索树是排序好的，而且插入新数据时，平均时间复杂度是 O(logn)。但当二叉搜索树极度不平衡时，二叉搜索树与排序的链表是相似的，插入数据的时间复杂度也提升至 O(n)。
使用二叉搜索树作为数据容器，插入数据的平均时间复杂度是 O(logn)，最差情况的时间复杂度是 O(n)，找出中位数的时间复杂度是 O(logn)，最差情况的时间复杂度是 O(n)。
思路 5：AVL 树和红黑树
这个算法的思路是：使用平衡的二叉搜索树（AVL 树或者红黑树）作为数据容器。AVL 树和红黑树都在某种程度上保证了二叉搜索树的左右子树在深度上差异不大，从而使得整棵二叉搜索树平衡。
使用 AVL 树和红黑树作为数据容器，插入数据的时间复杂度是 O(logn)，找出中位数的时间复杂度是 O(1)。
思路 6：最大堆和最小堆
之前的思路是希望对从数据流中读出的数据进行从头到尾彻底的排序，然后找出中位数。我们能不能找到一个办法不需要进行从头到尾的彻底的排序呢？当然可以。我们的目的是希望找到中位数，也就是说，比中位数小的数和比中位数大的数并不一定需要排序，只用确保这些数比中位数小或者大就行。
因此，这个算法的思路是：使用最大堆作为比中位数小的数的数据容器，使用最小堆作为中位数大的数的数据容器。最大堆的堆顶是这个数据容器中的最大值，最小堆的堆顶是这个数据容器中的最小值。这时，我们只需要保证两个数据容器的元素个数相差不超过 1，并且最大堆的堆顶小于最小堆的堆顶。
使用最大堆和最小堆作为数据容器，插入数据的时间复杂度是 O(logn)，找出中位数的时间复杂度是 O(1)。