首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >在Python中在O(log )时间内运行中位数

问在Python中在O(log )时间内运行中位数
EN

Stack Overflow用户
提问于 2021-08-27 06:44:00
回答 1查看 264关注 0票数 0

我试图在每次操作之后找到一组数字的运行中值,其中一个操作可以是以下内容之一:

添加x -在数字集合中添加数字x

remove x -从数字集合中移除数字x(假设x总是存在于集合中)

我的目标是在O(log )时间内执行每一个操作。如何在Python中实现这一点?在Python中有任何内置的构造来实现这一点吗?

如果只允许添加x操作,则可能的算法是维护minHeap (存储数字的下半部)和maxHeap (存储数字的上半部分),如这段视频中所解释的那样。但如果也允许删除x操作,则删除值将花费O(n)时间(O(n)用于线性搜索堆中的值,O(log )用于执行加/减键操作并弹出一个元素)。那么,如何处理在O(log )时间内删除值呢?

P.S. -我知道如何在C++中使用多集进行此操作。由于它们是作为平衡BST实现的,所以所有操作(插入、搜索和删除)都是O(log )。

EN

回答 1

Stack Overflow用户

发布于 2021-08-27 14:44:03

由于您提到了平衡BST作为一种可能的解决方案,因此您可以从实现BSTs或订单统计树(如分类容器 )的任何第三方模块获得所需的(最坏情况)时间限制。这有一个额外的好处,即已经在O(log )时间内提供了添加、删除和任意索引。

如果您的问题是如何具体使用两种堆方法(即较小一半的数字为max堆,对于较大的一半为最小的堆)来执行这些操作,则有两个可行的实现remove的选项:

  1. 使用支持减少键(例如Fibonnaci或Brodal堆)并保存指向所有值的指针的堆类型;这样做的好处是给出了最坏的情况O(log )删除,但是在Python的内置heapq库中是不可用的。
  2. 使用延迟删除将元素标记为“已删除”。这样做的缺点是,在摊销时间内只移除O(log ),而O(n)则是最坏的情况,但好处是只使用heapq及其二进制堆。

下面是带有heapq和Lazy删除的minhe-max堆方法的Python实现。重构策略类似于通过开放寻址解决哈希冲突的冲突,它是在两个堆上执行一次完整的传递,并在删除元素的比例超过50%时删除所有已删除的元素。

代码语言:javascript
复制
import collections
import heapq
import math
from typing import Union, List, Counter


class MedianHeap:
    def __init__(self):
        """ Data structure for holding numeric types, with O(log n) amortized insertion and deletion and
        constant worst case median finding.
        Maintains two heaps:
        a max heap with values smaller than (or eq. to) the median, and a
        min heap with values larger than (or eq. to) the median).
        We use lazy deletion from heaps (rebuilding them if more than ~50% of the heaps are deleted elements)
         to guarantee amortized insertion and deletion.

        The following class invariants are maintained before an external function call starts
        and after that function call ends:
            1. The front of each heap is either infinity (the empty heap sentinel), or a valid element
            2. All elements in self.max_heap have a value less than or equal to all elements in self.min_heap
            3. Size (i.e. undeleted elements) of self.min_heap is 0 or 1 plus the size of self.max_heap"""

        self.min_heap: List[Union[int, float]] = [math.inf]  # Add a sentinel value, to avoid repeated empty checks.
        self.max_heap: List[Union[int, float]] = [math.inf]  # on the left: all elements <= effective median

        self.total_real_elems: int = 0
        self.min_real_elems: int = 0
        self.max_real_elems: int = 0

        self.deleted: Counter[int, int] = collections.Counter()

        # If lazy deletion has caused our data structures to fill too much with deleted elements, trigger a rebuild
        # We rebuild if: (lazy_deletion_multiplier * #deleted) > total_size + lazy_deletion_constant.

        # By default, the multiplier is set at 50%, as is common for open-addressing hash tables which also use
        # lazy deletion. The constant can be increased based on performance needs.
        self.lazy_deletion_multiplier: int = 2
        self.lazy_deletion_constant: int = 500

    def insert(self, num: int) -> None:
        """Insert num into our MedianHeap. May not trigger a full rebuild. O(lg n) worst case time."""
        if not (-math.inf < num < math.inf):
            raise ValueError
        if self.total_real_elems == 0:
            heapq.heappush(self.min_heap, num)
            self.total_real_elems += 1
            self.min_real_elems += 1
            return None

        if num >= self.min_heap[0]:
            heapq.heappush(self.min_heap, num)
            self.min_real_elems += 1
        else:
            heapq.heappush(self.max_heap, -num)
            self.max_real_elems += 1

        self.total_real_elems += 1
        self._rebalance()
        return None

    def remove(self, num: int) -> None:
        """Change the status of one instance of 'num' from active to deleted. O(lg n) amortized, O(n) worst case time.
        num must be an active element in our data structure. May trigger a rebuild."""
        if num >= self.min_heap[0]:
            if num == self.min_heap[0]:
                heapq.heappop(self.min_heap)
            else:
                self.deleted[num] += 1
            self.min_real_elems -= 1
        else:
            if num == -self.max_heap[0]:
                heapq.heappop(self.max_heap)
            else:
                self.deleted[num] += 1
            self.max_real_elems -= 1

        self.total_real_elems -= 1
        self._rebalance()

    def _clean_min_heap_front(self) -> None:
        """While the front of the min_heap was already deleted, remove it from the min_heap"""
        while self.deleted[self.min_heap[0]] > 0:
            self.deleted[heapq.heappop(self.min_heap)] -= 1

    def _clean_max_heap_front(self) -> None:
        """While the front of the max_heap was already deleted, remove it from the max_heap"""
        while self.deleted[-self.max_heap[0]] > 0:
            self.deleted[-heapq.heappop(self.max_heap)] -= 1

    def _rebuild_fully(self) -> None:
        """To guarantee O(log n) amortized insertions and deletions with lazy deletions, we must detect when the number
        of removed elements still in our heap has grown too large: If so, perform an O(n) full rebuild of both heaps
        from scratch, clearing all previously removed elements."""

        # Rebuild heaps, trying to maintain size approximately based on the median
        approx_median: int = self.min_heap[0]

        new_min_heap: List[Union[int, float]] = [math.inf]
        new_max_heap: List[Union[int, float]] = [math.inf]

        for elem in self.max_heap:
            if self.deleted[-elem] > 0:
                self.deleted[-elem] -= 1
                continue
            elif math.isinf(elem):
                continue
            if -elem < approx_median:
                new_max_heap.append(elem)
            elif -elem > approx_median:
                new_min_heap.append(-elem)
            else:
                if len(new_min_heap) - len(new_max_heap) > 1:
                    new_max_heap.append(elem)
                else:
                    new_min_heap.append(-elem)

        for elem in self.min_heap:
            if self.deleted[elem] > 0:
                self.deleted[elem] -= 1
                continue
            elif math.isinf(elem):
                continue

            if elem < approx_median:
                new_max_heap.append(-elem)
            elif elem > approx_median:
                new_min_heap.append(elem)
            else:
                if len(new_min_heap) - len(new_max_heap) > 1:
                    new_max_heap.append(-elem)
                else:
                    new_min_heap.append(elem)

        self.min_heap = new_min_heap
        self.max_heap = new_max_heap

        heapq.heapify(self.min_heap)
        heapq.heapify(self.max_heap)

        self.deleted.clear()
        self.min_real_elems = len(self.min_heap) - 1
        self.max_real_elems = len(self.max_heap) - 1
        self.total_real_elems = self.min_real_elems + self.max_real_elems

        if not (0 <= (self.min_real_elems - self.max_real_elems) <= 1):
            self._rebalance()

    def _need_full_rebuild_check(self) -> bool:
        """Test whether our heaps have a larger fraction of removed elements than allowed"""
        total_size: int = len(self.min_heap) + len(self.max_heap)
        return (self.lazy_deletion_multiplier * (total_size - self.total_real_elems)
               > total_size + self.lazy_deletion_constant)

    def _rebalance(self):
        """ Restore the class invariants:
        1. Front of each heap is infinity (empty heap or sentinel), or a valid element
        2. All elements in self.max_heap have a value <= all elements in self.min_heap
        3. Size (i.e. undeleted elements) of self.min_heap - size of self.max_heap is 0 or 1"""

        if self._need_full_rebuild_check():
            self._rebuild_fully()
            return None

        self._clean_min_heap_front()
        self._clean_max_heap_front()

        while -self.max_heap[0] > self.min_heap[0]:
            if self.min_real_elems - self.max_real_elems <= -1:  # Prefer deleting from max_heap
                self.max_real_elems -= 1
                self.min_real_elems += 1
                heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
                self._clean_max_heap_front()

            else:  # Prefer deleting from min_heap
                self.max_real_elems += 1
                self.min_real_elems -= 1
                heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
                self._clean_min_heap_front()

        while self.min_real_elems - self.max_real_elems <= -1:  # Need to reduce size of max_heap
            self.max_real_elems -= 1
            self.min_real_elems += 1
            heapq.heappush(self.min_heap, -heapq.heappop(self.max_heap))
            self._clean_max_heap_front()  # Removing front of a heap may place a deleted element in front

        while self.min_real_elems - self.max_real_elems > 1:  # Need to reduce size of min_heap
            self.max_real_elems += 1
            self.min_real_elems -= 1
            heapq.heappush(self.max_heap, -heapq.heappop(self.min_heap))
            self._clean_min_heap_front()  # Removing front of min_heap may place a deleted element in front

        return None

    def calculate_median(self) -> float:
        """Calculate the median in constant time: the median element(s) are always in a heap's front."""
        if self.total_real_elems == 0:
            raise IndexError

        if self.total_real_elems % 2 == 0:
            return (self.min_heap[0] - self.max_heap[0]) / 2.0
        else:
            return self.min_heap[0]
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/68949041

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档