Arhlit - информационные технологии

как определить, больше ли k-й самый большой элемент кучи, чем x

Рассмотрим двоичную кучу, содержащую n чисел (в корне хранится наибольшее число). Вам дано натуральное число k ‹ n и число x. Вы должны определить, больше ли k-й самый большой элемент кучи, чем x или нет. Ваш алгоритм должен выполняться за время O(k). Вы можете использовать O(k) дополнительной памяти

algorithm complexity-theory binary-heap
07.02.2011

  • -1: это интересная проблема, но это неправильный способ задать вопрос. Пожалуйста, не копируйте здесь задание дословно. 07.02.2011

Ответы:


1

Простые dfs могут сделать эту работу. У нас есть счетчик, установленный на ноль. Начните с корня и на каждой итерации проверяйте значение текущего узла; если он больше x, то увеличиваем счетчик и продолжаем алгоритм для одного из дочерних узлов. Алгоритм завершается, если счетчик больше, чем равно 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, должен быть дочерним по отношению к посещенному узлу со значением больше x. Однако, поскольку каждый посещенный узел, кроме корня, должен иметь родителя со значением больше x, количество посещенных узлов со значением меньше x должно быть не более ((k-1)*2)-(k-1) = k -1, так как k-1 из (k-1)*2 дочерних элементов имеют значения больше, чем x. Это означает, что мы посещаем k узлов больше x и k-1 меньше x, что равно 2k-1.

07.02.2011
  • и запустить алгоритм для дочерних узлов В этом проблема. Как вы выбираете, с каким ребенком начать? Обратите внимание, что это не отсортированное двоичное дерево, это всего лишь куча. 07.02.2011
  • @ Саид Нет, с чего начать. В вашем коде вы просто просматриваете кучу слева направо. Но детей не сортируют! node.left может быть как меньше, так и больше, чем node.right. Есть изображение двоичной кучи. 07.02.2011
  • @Nikita Rybak, Children всегда меньше, чем их родитель, не важно, отсортированы они или нет, просто проверьте их, имеет ли родитель большее значение, если вы не уверены в этом простом алгоритме, добавьте к нему еще один счетчик и запустите его, он будет запускаться не более 3k раз. 07.02.2011
  • @Saeed Хорошо, просто рассмотрите картинку в Википедии (независимо от x). Ваш алгоритм объявит 19 вторым наибольшим значением, 17 - третьим, 2 - четвертым, 7 - пятым и так далее. Но все мы знаем, что это не так. 07.02.2011
  • @Nikita Rybak, я не нахожу k-й больший элемент, Вопрос: Вы должны определить, больше ли k-й по величине элемент в куче, чем x, если 2k-й по величине элемент больше, чем x, то наверняка k-й по величине элемент больше чем х. кого волнует k-й по величине элемент? просто заботьтесь о том, чтобы x был больше или нет. 07.02.2011
  • @Nikita Rybak - Он не объявляет, какой из них является k-м наибольшим, а только то, сколько элементов больше x. Куча сортируется в том смысле, что вам нужно рассматривать ее дочерние элементы только в том случае, если она больше самого x. Этот алгоритм правильный. 07.02.2011
  • @ Саид Хорошо, видимо, я не умею читать. Это, действительно, правильно. Молодец. 07.02.2011
  • @Nikita: Не кори себя. Название полностью вводит в заблуждение. 07.02.2011
  • @Саид: Спасибо за решение! В любом случае, что вы подразумеваете под счетчиком ссылок, и есть ли какая-то особая цель для использования счетчика ссылок вместо обычного значения int! 12.03.2011
  • Разве k-й самый большой элемент не может быть самым правым листом дерева (когда k равно или больше высоты кучи), что делает производительность в худшем случае O (n) или O (2 ^ k), а не В порядке)? 14.12.2011
  • @Eric Mickelsen, задан вопрос, чтобы определить, больше ли k-й по величине элемент кучи, чем x, или не найден K-й по величине элемент, поэтому, если вы найдете K элементов, которые больше, чем x, нет необходимости находить K-й по величине элемент, В случай, который просто меньше, чем K-й самый большой элемент, вы знаете, что все родители (на пути от корня до K-го самого большого элемента) больше этого, поэтому максимальная высота дерева до K-го самого большого элемента равна K, также вы просто проверяете дочерний элемент, если родитель больше, чем x (не более K раз), поэтому вы не проверяли более 3 * k узлов, пока не достигли K-го наибольшего элемента. 14.12.2011
  • @Саид Амири: Спасибо, это имеет смысл. Для меня гораздо логичнее визуализировать это как поиск k элементов, превышающих x - почему-то это не щелкнуло для меня. Разве вы на самом деле не гарантируете проверку не более 2 * k-1 узлов? 14.12.2011
  • @ Эрик Микельсен, кажется, вы правы, но сейчас я думал об этом (5 минут :), но вижу, что не могу это доказать (элегантным способом, а не индукцией). Если вы доказали это, не стесняйтесь редактировать мой ответ. 14.12.2011
  • @Saeed Amiri: количество посещенных узлов со значениями больше x будет не более k. Каждый узел, посещенный со значением меньше x, должен быть дочерним по отношению к посещенному узлу со значением больше x. Однако, поскольку каждый посещенный узел, кроме корня, должен иметь родителя со значением больше x, количество посещенных узлов со значением меньше x должно быть не более ((k-1)*2)-(k-1) = k -1, так как k-1 из (k-1)*2 дочерних элементов имеют значения больше, чем x. Это означает, что мы посещаем k узлов больше x и k-1 меньше x, что равно 2k-1. 14.12.2011
  • @EricMickelsen Вы правы, я добавил предложенное вами доказательство. 14.12.2011
  • @Saeed Amiri, я только что протестировал ваше решение CheckNode с максимальной кучей {11,9,8,6,1,4,3,2) с CheckNode(Node,4,5,счетчик ссылок) и передачей по счетчику ссылок переменная неверна (т.е. 0). Спасибо. 23.12.2011
  • @ Фрэнк, не могли бы вы сказать мне, какова была ваша отладочная информация? Также вы уверены, что у вас есть maxheap? 23.12.2011
  • @ Саид Амири, да, я уверен, что {11,9,8,6,1,4,3,2} - это максимальная куча. Кроме того, CheckNode не имеет рекурсивного базового случая. Наконец, вы уверены, что CheckNode правильно обрабатывает случай, когда x равен элементу max-heap? Спасибо. 23.12.2011
  • @Frank, вы можете видеть код, он не проверяет равенство, поэтому, если элемент равен максимальному значению кучи, он не учитывает его, но да {11,9,8,6,1,4,3,2} это максимальная куча, но как вы ее храните? Я имею в виду, какова ваша реализация дерева кучи или как вы выполняете итерацию по массиву? Лучше выложи свой код. 23.12.2011
  • @SaeedAmiri: Отличное решение, но есть идеи, почему вы return в counter >=k, а не counter ==k? 15.07.2014
  • @KodeSeeker, потому что это должен быть счетчик ссылок и вызывает изменения, я не знаю, почему я изменил ref на обычный вызов функции. 15.07.2014
  • Может ли кто-нибудь объяснить мне, как найти K элементов, которые больше, чем x , говорит, что X больше, чем K-й самый большой элемент? 10.11.2018
    • Новые материалы
    12 сайтов с искусственным интеллектом, которые поразят вас
    Приготовьтесь поразить воображение Сегодня существует несколько веб-сайтов, использующих искусственный интеллект (ИИ). От индивидуальных рекомендаций по новостям до более умных поисковых..
    Скрытый технический долг в системах машинного обучения [NeurIPS 2015]
    Что такое технический долг? Технический долг — это метафора, введенная Уордом Каннингемом в 1992 году, чтобы объяснить долгосрочные затраты, связанные с быстрым продвижением в разработке..
    Алгоритм быстрой сортировки в Python
    Всем привет, добро пожаловать на programminginpython.com . Здесь я покажу вам, как реализовать алгоритм быстрой сортировки в Python. В предыдущих статьях я рассмотрел Сортировку вставкой ,..
    Как использовать манипулирование объектами в JavaScript
    Объекты являются важным строительным блоком JavaScript. Они позволяют группировать свойства и методы вместе. Объект представляет собой набор свойств. Свойства идентифицируются с..
    Разработка игр с помощью Godot Engine: мощный инструмент с открытым исходным кодом
    Разработка игр — творческий и сложный процесс, требующий множества навыков и инструментов. Одним из наиболее важных инструментов является игровой движок, который представляет собой программную..
    От XML к аннотациям: переход к современной конфигурации Spring
    Введение Фреймворк Spring претерпел значительную эволюцию с момента своего создания. Одним из заметных изменений стал переход от конфигураций на основе XML к конфигурациям, управляемым..
    Я люблю Руби!
    Я люблю Руби! Мне это нравится по той же причине, по которой мне нравится программировать на Python. Он настолько интуитивно понятен, а встроенные методы упрощают решение проблем. Если вы..