剣はofferのデータストリームの中位数を指す

データ・ストリームの中央値

題

解題構想

Pythonコード

運転結果

タイトル
データ・ストリームの中位数を取得するにはどうすればいいですか?データストリームから奇数個の数値を読み出すと、中位数は、すべての数値がソートされた後に中間に位置する数値である.データストリームから偶数個の数値が読み出されると、中位数は、すべての数値が並べ替えられた後の中間の2つの数の平均値となります.Insert()メソッドを使用してデータストリームを読み出し、getMedian()メソッドを使用して現在の読み出しデータの中位数を取得します.
問題を解く構想.
我々の目標は,データの中位数を見つけることであり,それ以外のデータの配列順序には注目する必要はない.スタックで実現することを考慮することができます:それぞれ1つの大きいトップスタックと1つの小さいトップスタックを構築して、大きいトップスタックの中でデータストリームの中で最小のn/2個のデータを保存して、それではそのトップ要素は中位数です;小さなトップスタックは、データストリームの最大n/2個のデータを保存します.
どのように大きいトップスタックと小さいトップスタックの要素の個数が等しいことを保証します:新しく来たデータの各スタックは順番に挿入して、奇数番目の要素は大きいトップスタックを挿入して、偶数の要素は小さいトップスタックを挿入して、このように両側の要素が等しいことを保証します.
どのように大頂堆の中で保存するのが最小のn/2個の元素であることを保証します:私たちが新しい元素を挿入した後、大頂堆と小頂堆の堆頂元素を比較して、大頂堆の堆頂が小頂堆の堆頂より大きい時、私たちは2つの堆頂を取り出して、別の堆の中に保存します.心の中で黙念します:大きい頂上は最小のn/2の元素を積み上げて、小さい頂上は最大のn/2の元素を積み上げます.注意:元素を取る時くれぐれも直接popを取ってはいけなくて、取り出した後の山が依然として大きい頂の山であることを保証します|小さい頂の山
どのように中位数を見つけるか:奇数番目の要素に大きなトップスタックを挿入する必要があります.そのため、データストリームの長さが奇数の場合、大きなトップスタックは小さなトップスタックより1つの要素が多く、大きなトップスタックのトップは中位数です.データストリームの長さが偶数の場合、大きなトップスタックと小さなトップスタックのサイズは同じであり、大きなトップスタックと小さなトップスタックのトップ要素の平均値は中位数である.
スタック挿入操作(大トップスタックの例):新しい要素を大トップスタックの最後に配置し、親ノードと比較し、親ノードより大きい場合は交換します.交換した場合は、ルートノードまで新しい親ノードとどちらが大きいかを考慮します.
削除操作(大頂スタックの例):スタック要素を削除するときは、まずスタック要素と最後の要素を交換し、新しいスタック要素とその2つのサブノードを比較します.スタック要素がサブノードより小さい場合は、そのサブノードの大きなノードで皇位を継承します.子供ノードがなくなるまで新しい子供と比較し続けます
Pythonコード

class MedianOfFlowing:
    '''
             
    '''
    def __init__(self):
        self.length = 0
        self.maxHeap = []
        self.minHeap = []
    
    def popMaxHeap(self):
        try:
            num, self.maxHeap[0] = self.maxHeap[0], self.maxHeap[-1]
            self.maxHeap = self.maxHeap[:len(self.maxHeap)-1]
            maxLen = len(self.maxHeap)
            if maxLen > 1:
                i = 0
                while i < maxLen // 2:
                    maxIndex = i * 2 + 1
                    if maxLen > maxIndex+1 and self.maxHeap[maxIndex+1] > self.maxHeap[maxIndex]:
                        maxIndex += 1
                    if self.maxHeap[i] < self.maxHeap[maxIndex]:
                        self.maxHeap[i], self.maxHeap[maxIndex] = self.maxHeap[maxIndex], self.maxHeap[i]
                    i = maxIndex
            return num
        except Exception:
            print("popMaxHeap Error: The flowing is None")

    def popMinHeap(self):
        try:
            num, self.minHeap[0] = self.minHeap[0], self.minHeap[-1]
            self.minHeap = self.minHeap[:len(self.minHeap)-1]
            minLen = len(self.minHeap)
            if minLen > 1:
                i = 0
                while i < minLen // 2:
                    minIndex = i * 2 + 1
                    if minLen > minIndex+1 and self.minHeap[minIndex+1] < self.minHeap[minIndex]:
                        minIndex += 1
                    if self.minHeap[i] > self.minHeap[minIndex]:
                        self.minHeap[i], self.minHeap[minIndex] = self.minHeap[minIndex], self.minHeap[i]
                    i = minIndex
            return num
        except Exception:
            print("popMinHeap Error: The flowing is None")

    def insertMaxHeap(self, num):
        self.maxHeap.append(num)
        index = len(self.maxHeap) - 1
        while (index-1) // 2 >= 0:
            if self.maxHeap[index] > self.maxHeap[(index-1)//2]:
                self.maxHeap[index], self.maxHeap[(index-1)//2] = self.maxHeap[(index-1)//2], self.maxHeap[index]
                index = (index-1) // 2
            else:
                break

    def insertMinHeap(self, num):
        self.minHeap.append(num)
        index = len(self.minHeap) - 1
        while (index-1) // 2 >= 0:
            if self.minHeap[index] < self.minHeap[(index-1)//2]:
                self.minHeap[index], self.minHeap[(index-1)//2] = self.minHeap[(index-1)//2], self.minHeap[index]
                index = (index-1) // 2
            else:
                break


    def insert(self, num):
        if num:
            self.length += 1
        #           
        if self.length % 2:
            self.insertMaxHeap(num)
        else:
            self.insertMinHeap(num)

        #                  ，    
        if self.maxHeap and self.minHeap and self.maxHeap[0] > self.minHeap[0]:
            minVal, maxVal = self.popMinHeap(), self.popMaxHeap()
            self.insertMaxHeap(minVal)
            self.insertMinHeap(maxVal)
    
    def getMedian(self):
        '''
             ，           ，                    
        '''
        try:
            if self.length % 2:
                return self.maxHeap[0]
            else:
                return (self.maxHeap[0] + self.minHeap[0]) / 2.0
        except Exception:
            print("getMedian Error: The flowing is None")

if __name__ == '__main__':
    data = [1,4,7,3,5,1,7,2,8,2,6]
    median = MedianOfFlowing()
    for num in data:
        print(f"   {num}")
        median.insert(num)
        print(f"       {median.length},     {median.maxHeap},    {median.minHeap}")
        print(f"          {median.getMedian()}")

実行結果

          1
   4
       2,     [1],    [4]
          2.5
   7
       3,     [4, 1],    [7]
          4
   3
       4,     [3, 1],    [4, 7]
          3.5
   5
       5,     [4, 1, 3],    [5, 7]
          4
   1
       6,     [3, 1, 1],    [4, 7, 5]
          3.5
   7
       7,     [4, 3, 1, 1],    [5, 7, 7]
          4
   2
       8,     [3, 2, 1, 1],    [4, 5, 7, 7]
          3.5
   8
       9,     [4, 3, 1, 1, 2],    [5, 7, 7, 8]
          4
   2
       10,     [3, 2, 1, 1, 2],    [4, 5, 7, 8, 7]
          3.5
   6
       11,     [4, 2, 3, 1, 2, 1],    [5, 6, 7, 8, 7]
          4