Чтобы глубоко понять проблему TOP K, мы должны сначала по-настоящему понять концепцию «кучи».
Определение кучи
Чтобы стать кучей, должны быть выполнены как минимум два следующих условия.
- Это должно быть полное бинарное дерево (если вы не знаете, что такое полное бинарное дерево, вы можете Baidu или прочитать мою последнюю статью)
- Значение любого узла должно быть больше или меньше значения всех узлов в его поддереве. Эти два случая соответствуют большой верхней куче и маленькой верхней куче соответственно.
Вот 2 примера:
Как реализовать кучу?
Как упоминалось в предыдущей статье, полное бинарное дерево очень подходит для реализации таких структур данных, как массивы. Таким образом, куча как полное бинарное дерево, безусловно, является наиболее подходящей реализацией с массивом.
И правила тоже очень простые, резюмируем еще раз:
Если нижний индекс узла равен i, то нижний индекс его левого дочернего узла равен 2i, а нижний индекс правого дочернего узла равен 2i+1.
Родительский узел - i/2.
Если вы не понимаете упомянутую выше взаимосвязь отображения полного бинарного дерева и массива, вы можете прочитать предыдущую статью или нарисовать рисунок самостоятельно.
Реализация кучи — это не что иное, как завершение операции вставки данных и удаления данных в куче.
Алгоритм вставки
Работа вставки действительно проста, мы можем посмотреть на картинку только сейчас, принимая эту большую кучу в качестве примера. Предположим, мы вставляем значение, мы впервые вставляем это значение в этом Конечное положение кучи, а затем сравните это значение с его родительским узлом, если оно больше, чем родительский узел, а затем поменяйте позицию, если оно меньше, чем родительский узел, то вставьте его полностью.
Например, мы вставляем 10 данных в большую кучу,
Видно, что этовверх дномАлгоритм вставки все еще хорошо изучен.
Удалить верхний элемент алгоритма кучи
Согласно определению большой верхней кучи и маленькой верхней кучи, мы можем знать, что верхний элемент кучи всегда является самым большим или самым маленьким. Затем, после удаления верхнего элемента кучи, значение нового верхнего элемента кучи, естественно, Получается, что левый и правый потомки верхнего элемента кучи теперь равны.
Итак, видимо, мы наивно думали, что алгоритм удаления верхнего элемента кучи должен быть (предполагая большую верхнюю кучу):
После удаления верхнего элемента кучи мы сравниваем значение левого сына со значением правого сына, и тот, у кого значение больше, пойдет на вершину кучи, чтобы остаться. После того, как мой сын поднялся на вершину кучи,
Сын сына также аналогичен описанной выше операции, и тот, кто старше, переместится на позицию выше. Кажется, что алгоритм неуязвим и прост для понимания, но этот алгоритм прост
Возникает следующее исключение.
Таким образом, можно видеть, что приведенный здесь алгоритм в некоторых случаях приведет к уничтожению полного двоичного дерева кучи.
Поэтому мы хотим его улучшить.Улучшенный алгоритм выглядит следующим образом:
Если вы хотите удалить верхний элемент кучи, сначала удалите верхний элемент кучи, а затем поместите данные последней позиции кучи в верхнюю часть кучи, а затем сравните размеры сверху вниз и обменяйте позиции.
Давайте посмотрим на схему этого алгоритма:
Очевидно, что этот алгоритм позволит избежать проблемы дыр в массиве, вызванной первым алгоритмом.
Реализована ли легендарная сортировка кучей с использованием этой кучи и как?
Да, куча в heapsort использует эту кучу для реализации структуры данных. Это немного сложно реализовать, поэтому давайте кратко о нем (я не буду вдаваться в подробности, потому что сортировка кучи действительно не используется):
Учитывая неупорядоченный массив, спросите, как использовать структуру данных кучи для сортировки?
Для этого неупорядоченного массива предпочтительнее построить кучу.Алгоритм вставки данных был упомянут ранее.Для этого неупорядоченного массива можно считать, что первый элемент массива является позицией вершины кучи, а затем положить следующие элементы могут быть вставлены по очереди в соответствии с нашим алгоритмом вставки. (На самом деле есть и более дружественные методы построения куч, но сегодня речь не об этом. Заинтересованные учащиеся могут поискать их самостоятельно)
С этой кучей как сортировать? Предположим, что это куча с большой вершиной. Фактически, сортировка этой кучи похожа на наш алгоритм удаления верхнего элемента кучи. После удаления верхнего элемента кучи не достигает ли второй десяток элементов вершины? И так далее. . .
Почему не используется сортировка кучей?
На самом деле, производительность сортировки в куче "вроде бы нормальная", а удельная временная сложность такая же, как и у быстрой сортировки, временная сложность O(nlogn), и это по-прежнему стабильный алгоритм сортировки. Но у этой штуки есть фатальный недостаток:
Работа кучи слишком сильно зависит от операции подкачки.Похоже, что временная сложность такая же, как и у быстрой сортировки, но из-за слишком большого количества перестановок фактическая производительность намного хуже, чем у быстрой сортировки.
Это как соревнования по тяжелой атлетике, у всех одинаковые результаты, ты немного тяжелее меня, и, конечно же, я чемпион.
Многословен давно, сортирует такую фигню, зачем вы про него?
Я рожден быть полезным, бро, в этом деле не разберешься, но и другие вещи могут быть полезны.
Очереди с приоритетами почти такие же, как «кучи»
Так называемая приоритетная очередь означает, что независимо от порядка входа порядок выхода основан на приоритете.Тщательно подумайте, совпадает ли он с определением нашей кучи big top или small top heap. Бесконечно сходится? Учащиеся, знакомые с Android и прочитавшие исходный код volley, должны знать, что PriorityBlockingQueue в volley не является потокобезопасным. Это приоритетная очередь, сформированная такой структурой данных, как куча?
Давайте снова посмотрим на классическую задачу TOP K.
С приведенным выше основанием гораздо проще взглянуть на проблему TOP K. литкод 703 вопросы:Lee TCO's-talent.com/problems/conditioning…
Проще говоря, вам дается массив, и каждый раз, когда вы вставляете данные, вас просят вернуть K-й самый большой элемент в массиве.
Вот как решить эту проблему:
1. Каждый раз, когда в массив вставляется кусок данных, мы выполняем быструю сортировку, а затем вынимаем k-й размер. Это самый простой, но глупый способ сделать это. Потому что каждый раз, когда вы вставляете данные, вам приходится сортировать их все, что слишком медленно.
- Зная, что существует такая вещь, как приоритетная очередь, мы можем поддерживать небольшую верхнюю кучу размера k, и каждый раз, когда приходит новый элемент, мы смотрим на новый элемент. Является ли значение больше, чем значение этой маленькой верхней кучи, если оно больше его, то удалите верхний элемент этой маленькой верхней кучи, а затем вставьте значение нашего нового элемента, Затем возьмите верхний элемент этой маленькой верхней кучи, который является нашим k-м самым большим элементом.
class KthLargest {
PriorityQueue<Integer> queue;
int maxHeapSize;
public KthLargest(int k, int[] nums) {
//初始化一个大小为k的小顶堆
queue = new PriorityQueue<Integer>(k);
maxHeapSize=k;
if (k < nums.length) {
//先构造一个大小为k的 堆
for (int i = 0; i < k; i++) {
queue.add(nums[i]);
}
//下面构造的时候要判断大小
for (int j = k; j < nums.length; j++) {
if (nums[j] > queue.peek()) {
queue.poll();
queue.offer(nums[j]);
} else {
}
}
} else {
for (Integer integer : nums) {
queue.add(integer);
}
}
}
public int add(int val) {
if(queue.size()<maxHeapSize)
{
queue.offer(val);
return queue.peek();
}
if (val > queue.peek()) {
queue.poll();
queue.offer(val);
}
return queue.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/
Взгляните на эффект:
Хм, хорошо.
Затем, наконец, посмотрите на проблему leetcode 239.Lee TCO's-talent.com/problems/forget it…
С очередью с приоритетом эта проблема упростилась. Пока вы поддерживаете большую верхнюю кучу при обходе массива, проблема решена. (Код не на нем, он очень простой)
Конечно, на самом деле есть лучшее решение этой проблемы, то есть вместо кучи используется двусторонняя очередь, которую могут изучить заинтересованные студенты.
Есть ли реальная производственная проблема, которую может решить куча или очередь с приоритетом?
На самом деле есть много производственных задач, которые можно решить, например, мы делаем кастомную систему Android, допустим, у пользователя есть N задач, и каждая задача имеет определенное время выполнения. Когда пришло время выполнять пользовательские задачи, такие как будильник. Так как же выполнить это требование?
Проверяйте список задач каждую секунду.Соответствует ли время текущему времени? Очевидно, что нет, это слишком неэффективно.
Мы можем хранить эти задачи в виде небольшой верхней кучи, так что пока системное время проходит одну секунду, мы можем видеть, совпадает ли оно со временем верхнего элемента кучи.