如何判断堆中第k大元素是否大于x

发布于 2024-10-16 00:39:50 字数 121 浏览 3 评论 0原文

考虑一个包含 n 的二叉堆 数字(根存储最大的数字)。你被赋予了一个 正整数 k < n 和数字 x。你必须确定是否 堆中第 k 大的元素是否大于 x。你的 算法必须花费 O(k) 时间。您可以使用 O(k) 额外存储空间

Consider a binary heap containing n
numbers (the root stores the greatest number). You are given a
positive integer k < n and a number x. You have to determine whether
the kth largest element of the heap is greater than x or not. Your
algorithm must take O(k) time. You may use O(k) extra storage

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

轻拂→两袖风尘 2024-10-23 00:39:51
public class KSmallest2 {

private MinPQ<Integer> minHeap;
private int x;
private int k;
private int count = 0;

public KSmallest2(String filename, int x, int k) {
    this.x = x;
    this.k = k;
    minHeap = new MinPQ<>();
    try {
        Scanner in = new Scanner(new File(filename));
        while (in.hasNext()) {
            minHeap.insert(in.nextInt());
        }
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
}

public boolean check(int index) {

    if (index > minHeap.size()) {
        return false;
    }

    if (minHeap.getByIndex(index) < x) {
        count++;
        if (count >= k) {
            return true;
        }

        return  check(2 * index) ||
                check(2 * index + 1);
    }

    return false;
}



public static void main(String[] args) {
    KSmallest2 ks = new KSmallest2("src/main/resources/minheap.txt", 18, 5);
    System.out.println(ks.minHeap);

    System.out.println(ks.check(1));
}

}

public class KSmallest2 {

private MinPQ<Integer> minHeap;
private int x;
private int k;
private int count = 0;

public KSmallest2(String filename, int x, int k) {
    this.x = x;
    this.k = k;
    minHeap = new MinPQ<>();
    try {
        Scanner in = new Scanner(new File(filename));
        while (in.hasNext()) {
            minHeap.insert(in.nextInt());
        }
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
}

public boolean check(int index) {

    if (index > minHeap.size()) {
        return false;
    }

    if (minHeap.getByIndex(index) < x) {
        count++;
        if (count >= k) {
            return true;
        }

        return  check(2 * index) ||
                check(2 * index + 1);
    }

    return false;
}



public static void main(String[] args) {
    KSmallest2 ks = new KSmallest2("src/main/resources/minheap.txt", 18, 5);
    System.out.println(ks.minHeap);

    System.out.println(ks.check(1));
}

}

别挽留 2024-10-23 00:39:50

简单的 dfs 就可以完成这项工作。我们有一个计数器设置为零。从根开始,每次迭代检查当前节点的值;如果大于x,则增加计数器并继续对子节点之一进行算法。如果 counter 大于等于 k ​​或者没有剩余节点可供检查,则算法终止。运行时间为 O(k),因为最多迭代 k 个节点,并且每次迭代的时间复杂度为 O(1)。

伪代码如下所示。

    void CheckNode(Node node,int k, int x, ref int counter)
    {
        if (node.value > x)
        {
            counter++;
            if (counter >= k)
                return;

            CheckNode(node.Left, k, x, ref counter);
            CheckNode(node.Right,k, x, ref counter);
        }
    }

使用它:

        counter = 0;
        CheckNode(root,index,val,counter );
        if (counter >= index)
            return true;
        return false;

如果node.value < x 则所有子值都小于 x,无需检查。

正如 @Eric Mickelsen 在评论中提到的,最坏情况运行时间恰好是 2k-1 (k>0),如下所示。

访问的值大于x的节点的数量最多为
k.每个访问过的值小于 x 的节点都必须是 a 的子节点
访问过的节点的值大于 x。然而,由于每个节点
访问过,但根必须有一个值大于 x 的父级,
访问的值小于 x 的节点数量最多为
((k-1)*2)-(k-1) = k-1,因为 (k-1)*2 个子级中的 k-1 个具有值
大于x。这意味着我们访问大于 x 的 k 个节点,并且
k-1 小于 x,即 2k-1。

Simple dfs can do the job. We have a counter set to zero. Start from the root and in each iteration check the value of current node; if it is greater than x, then increase the counter and continue the algorithm for one of the child nodes. The algorithm terminates if counter is bigger than equal k or if there is no node left to check. The running time is O(k) because at most k node will be iterated and each iteration is in O(1).

A pseudo-code looks like as follows.

    void CheckNode(Node node,int k, int x, ref int counter)
    {
        if (node.value > x)
        {
            counter++;
            if (counter >= k)
                return;

            CheckNode(node.Left, k, x, ref counter);
            CheckNode(node.Right,k, x, ref counter);
        }
    }

use it:

        counter = 0;
        CheckNode(root,index,val,counter );
        if (counter >= index)
            return true;
        return false;

if node.value < x then all children values are smaller than x and there is no need to check.

As @Eric Mickelsen mentioned in comments worst case running time is exactly 2k-1 (k>0) as follows.

The number of nodes visited with values greater than x will be at most
k. Each node visited with value less than x must be a child of a
visited node with value greater than x. However, because every node
visited except the root must have a parent with value greater than x,
the number of nodes of value less than x visited must be at most
((k-1)*2)-(k-1) = k-1, since k-1 of the (k-1)*2 children have values
greater than x. This means that we visit k nodes greater than x and
k-1 less than x, which is 2k-1.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文