Куча – это особый тип двоичного дерева, который соответствует следующим критериям:
- Является полным бинарным деревом;
- Значение каждого узла должно быть не больше (или не меньше) значения его дочерних узлов.
Куча имеет следующие свойства:
- Вставка элемента в кучу имеет временную сложность
O(logN); - Удаление элемента из кучи имеет временную сложность
O(logN); - Максимальное/минимальное значение в куче можно получить с временной сложностью
O(1).
Тип кучи
- Максимальная куча: каждый узел в куче имеет значение не меньше его дочерних узлов. Следовательно, верхний элемент (корневой узел) имеет наибольшее значение в куче.
- Минимальная куча: каждый узел в куче имеет значение не больше, чем его дочерние узлы. Таким образом, верхний элемент (корневой узел) имеет наименьшее значение в куче.
Реализация кучи в JavaScript
Далее мы реализуем кучу. конструктор возьмет компаратор, который определит порядок элементов в куче (минимум или максимум)
Концепции:
Следите за комментариями в коде.
Код:
Выход:
Максимальная куча:
[ 6, 5, 5, 4, 3, 3, 2, 2, 1 ]
Минимальная куча
[ 1, 2, 2, 3, 3, 4, 5, 5, 6 ]
Вы можете видеть, что все возвращаемые данные находятся в порядке приоритета.
Практические вопросы
Задача: K-й самый большой элемент в массиве
Учитывая массив целых чисел nums и целое число k, вернуть самый большой kth элемент в массиве.
Обратите внимание, что это kth самый большой элемент в отсортированном порядке, а не kth отдельный элемент.
Вы должны решить ее за O(n) временную сложность.
Пример 1:
Input: nums = [3,2,1,5,6,4], k = 2 Output: 5
Пример 2:
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4 Output: 4
Решение
const findKthLargest = function(nums, k) {
const heap = new MaxHeap();
nums.forEach(num => heap.push(num));
for(let i = 0;i< k-1;i++){
heap.pop();
}
return heap.pop();
};
