时间戳

首页 > 解决方案 > 前 k 个最大元素插入 O(logn) 和 O(k) 的数据结构

algorithm - 前 k 个最大元素插入 O(logn) 和 O(k) 的数据结构

问题描述

我在数据结构类中被要求找到适合这些需求的数据结构：

Insert(S,num) - Insert to S a num in a O(log(n)) complexion time

PrintMax_k(S) - Print the k (constant) first biggest elemnts in some order(doesnt matter) in a O(k) complexion time

PrintAll(S) - Print all elemnts in some order(doesnt matter) in a O(n) complexion time

我需要使用什么类型的数据结构？

标签： algorithmsortingdata-structurestime-complexity

解决方案

由于k被假定为常数，您可以将此数据结构创建为包含H最多k个元素的最小堆（在数组数据结构中实现）和具有A任意顺序的剩余元素（如果有）的标准数组的组合.

操作如下：

Insert(S,num): 
    if size(H) < k:
        H.insert(num)
    else if H[0] < num: # compare with root value of heap, which is its minimum, at index 0
        A.append(H[0])
        H[0] := num # replace root value
        H.heapify() # sift down num, so heap property is restored
   else:
        A.append(num)

有关堆的 insert 和 heapify 方法的实现，请参阅Wikipedia 上的Binary Heap或其他地方。

在任何调用之后Insert，H将插入迄今为止的k个最大值。任何溢出（较小的值）都将在A.

PrintMax_k(S):
    for i in 0..size(H)-1: # simply iterate over the heap (which is an array)
        print H[i]

最后：

PrintAll(S):
    PrintMax_k(S) # call the above function
    for i in 0..size(A)-1:
        print A[i]

推荐阅读