Алгоритмы с нуля

Топ-K и k-й по величине элемент

Суть Найди k наибольших элементов эффективно: держи мин-кучу размера k. Добавляй элемент, выкидывай минимум если превышено k. Результат: O(n log k) время, O(k) память против O(n log n) для сортировки. Потоковая обработка без хранения всех данных.

◷ 32 min

У тебя есть поток чисел. Ты хочешь знать k наибольших. Наивный ответ: жди все числа, отсортируй их, возьми последние k. Но это O(n log n) время и O(n) память — ты сохраняешь всё. Ключевое: ты заботишься только о топ k, так что держи мин-кучу размера k. Добавляй каждое число. Когда куча превышает k элементов, вытащи наименьший (минимум). В конце твоя куча держит ровно k наибольших, и её корень это граница — k-й по величине элемент. Время: O(n log k). Память: O(k). Когда k малО, это разбивает сортировку.

Цель

После этого урока ты можешь решить проблему k-наибольших используя мин-кучу размера k: добавляй каждый элемент и выкидывай минимум когда куча растёт за k. Ты понимаешь почему это работает: куча всегда держит k кандидатов, и корень это k-й по величине. Ты можешь объяснить сложность времени O(n log k) и сложность памяти O(k), и почему это бьёт сортировку O(n log n) когда k ≪ n. Ты можешь узнать паттерны «k-й наибольший» и «топ k по частоте» на LeetCode и других платформах, и применить одинаковый подход на куче. Ты можешь кодировать это в один проход (нет фазы сортировки), и отследить алгоритм на конкретном массиве шаг за шагом.

Идея

Проблема: найди k наибольших (или k наименьших)

Дан массив чисел. Задача: найти k наибольших элементов. Например:

Массив: [3, 2, 1, 5, 6, 4], k = 2 → ответ: [5, 6]
Массив: [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4 → ответ: [5, 5, 6, 4] (или [6, 5, 5, 4], порядок может отличаться)

Наивный подход: сортировка

Отсортируй массив и возьми последние k элементов. Время: O(n log n), память: O(1) если на месте или O(n) с внешним хранилищем.

Проблема: ты должен отсортировать весь массив, хотя ты заботишься только о топ k. Когда k малО, это тратит работу впустую.

Ключевое для кучи: держи кучу размера k

Держи мин-кучу размера ровно k. Эта куча всегда будет содержать k наибольших элементов, видимых до сих пор.

Алгоритм:

Для каждого элемента в массиве:
- Добавь элемент в мин-кучу.
- Если размер кучи превышает k, вытащи минимум.
После обработки всех элементов, куча содержит ровно k наибольших.
Корень мин-кучи это k-й по величине элемент (наименьший из топ k).

Почему мин-куча, а не макс-куча? Потому что ты хочешь выкинуть наименьшего кандидата когда у тебя слишком много. Корень мин-кучи это наименьший, так что ты вытаскиваешь его немедленно.

Почему это работает?

В любой момент, куча держит k наибольших элементов видимых до сих пор. Когда приходит новый элемент:

Если он больше чем корень, он принадлежит топ k, так что ты удаляешь текущий минимум (корень) и вставляешь новый элемент.
Если он меньше чем корень, он не в топ k, так что ты игнорируешь его.

После обработки всех n элементов, куча держит k наибольших глобально. Корень это граница: это наибольший элемент среди топ k что может быть выкинут, то есть k-й по величине.

Пример: найди 2 наибольших в [3, 2, 1, 5, 6, 4]

Мин-куча размера k=2:

Добавь 3: куча = [3]. Размер = 1 < k, продолжи.
Добавь 2: куча = [2, 3]. Размер = 2 = k, продолжи.
Добавь 1: куча = [1, 3, 2]. Размер = 3 > k, вытащи минимум (1). куча = [2, 3].
Добавь 5: куча = [2, 3, 5]. Размер = 3 > k, вытащи минимум (2). куча = [3, 5].
Добавь 6: куча = [3, 5, 6]. Размер = 3 > k, вытащи минимум (3). куча = [5, 6].
Добавь 4: куча = [4, 5, 6]. Размер = 3 > k, вытащи минимум (4). куча = [5, 6].

Финальная куча: [5, 6]. k наибольших это 5 и 6. ✓

Симметричная проблема: найди k наименьших

Если хочешь k наименьших элементов, используй макс-кучу размера k. Логика идентична: когда куча превышает k, вытащи максимум (корень). В конце, куча держит k наименьших, и корень это k-й наименьший.

Частый паттерн: k-й по величине элемент

Часто проблема просит только k-й по величине элемент, не все k. После построения кучи, верни heap.peek() (корень) — это k-й по величине.

Частый паттерн: топ k по частоте

Дан массив, найди k самых частых элементов. Решение:

Посчитай частоту каждого элемента (хеш-таблица).
Построй мин-кучу размера k на частотах (не элементах).
Выкидывай наименее частый когда куча превышает k.
Куча содержит k самых частых элементов.

Это прямое применение одинакового паттерна.

Код

Топ-k используя мин-кучу


      1
      function topK(arr, k) {
    

      2
      // Мин-куча (очередь с приоритетом с меньшими значениями имеющими выше приоритет)
    

      3
      const minHeap = new MinPriorityQueue();
    

      4
       
    

      5
      // Добавляй каждый элемент и выкидывай минимум если куча превышает k
    

      6
      for (const num of arr) {
    

      7
        minHeap.insert(num, num); // insert(value, priority)
    

      8
        if (minHeap.size() > k) {
    

      9
          minHeap.extractMin(); // Удали наименьший
    

      10
        }
    

      11
      }
    

      12
       
    

      13
      // Вытащи все элементы из кучи (они в порядке кучи, не отсортированы)
    

      14
      const result = [];
    

      15
      while (!minHeap.isEmpty()) {
    

      16
        result.push(minHeap.extractMin());
    

      17
      }
    

      18
      return result;
    

      19
      }
    

      20
       
    

      21
      // Пример
    

      22
      const arr = [3, 2, 1, 5, 6, 4];
    

      23
      const k = 2;
    

      24
      const topTwoLargest = topK(arr, k);
    

      25
      console.log(topTwoLargest); // [5, 6] (порядок может отличаться; оба в куче)

L2 Мин-куча (очередь с приоритетом с мин в корне). Размер останется ≤ k.
L5 Для каждого элемента в массиве.
L6 Добавь элемент с приоритет = значение (меньший приоритет = выше приоритет).
L7 Если размер кучи превышает k, наименьший элемент (корень) удалён.
L12 Вытащи все оставшиеся элементы. Потому что это куча (не отсортированный массив), порядок может не быть строго возрастающий, но все k наибольших присутствуют.

Нахождение k-го по величине элемента

class MinPriorityQueue {
constructor() {
  this.heap = [];
}

insert(value) {
  this.heap.push(value);
  this.siftUp(this.heap.length - 1);
}

extractMin() {
  const root = this.heap[0];
  this.heap[0] = this.heap[this.heap.length - 1];
  this.heap.pop();
  if (this.heap.length > 0) {
    this.siftDown(0);
  }
  return root;
}

peek() {
  return this.heap[0];
}

isEmpty() {
  return this.heap.length === 0;
}

size() {
  return this.heap.length;
}

siftUp(index) {
  while (index > 0) {
    const parentIndex = Math.floor((index - 1) / 2);
    if (this.heap[index] < this.heap[parentIndex]) {
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    } else {
      break;
    }
  }
}

siftDown(index) {
  while (true) {
    const left = 2 * index + 1;
    const right = 2 * index + 2;
    let smallest = index;

if (left < this.heap.length && this.heap[left] < this.heap[smallest]) {
      smallest = left;
    }
    if (right < this.heap.length && this.heap[right] < this.heap[smallest]) {
      smallest = right;
    }

if (smallest !== index) {
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    } else {
      break;
    }
  }
}
}

// Найди k-й по величине элемент
function findKthLargest(arr, k) {
const minHeap = new MinPriorityQueue();

for (const num of arr) {
  minHeap.insert(num);
  if (minHeap.size() > k) {
    minHeap.extractMin();
  }
}

// Корень это k-й по величине
return minHeap.peek();
}

// Пример
const arr = [3, 2, 1, 5, 6, 4];
const k = 2;
const kthLargest = findKthLargest(arr, k);
console.log("The " + k + "-th largest element:", kthLargest);

const arr2 = [3, 2, 1, 5, 6, 4];
const k2 = 4;
const kthLargest2 = findKthLargest(arr2, k2);
console.log("The " + k2 + "-th largest element:", kthLargest2);

Output

Пошаговый разбор


      1
      const arr = [3, 2, 1, 5, 6, 4];
    

      2
      const k = 2;
    

      3
      const minHeap = new MinPriorityQueue();
    

      4
      for (const num of arr) {
    

      5
        minHeap.insert(num);
    

      6
        if (minHeap.size() > k) minHeap.extractMin();
    

      7
      }

Сложность

Топ-K используя мин-кучу размера k

Для каждого из n элементов в массиве:

Insert: O(log k) (куча имеет максимум k+1 элементов перед pop).
ExtractMin (когда куча превышает k): O(log k).

Итого: n итераций × O(log k) за итерацию = O(n log k) время.

Память: Куча держит максимум k элементов, так что O(k) память.

Сравнение с сортировкой

Если отсортируешь весь массив: O(n log n) время, O(1) вспомогательная память (если на месте).

Топ-K с кучей: O(n log k) время, O(k) память.

Когда подход кучи лучше?

Если k ≪ n (k намного меньше чем n), тогда log k ≪ log n, так O(n log k) ≪ O(n log n).
Если k близко к n, сортировка может быть проще и быстрее на практике.

Пример:

n = 1,000,000, k = 10: O(n log k) = O(1,000,000 × 3.3) ≈ 3.3 миллиона операций. O(n log n) = O(1,000,000 × 20) ≈ 20 миллионов операций. Куча быстрее.
n = 1,000, k = 500: O(n log k) = O(1,000 × 9) ≈ 9,000. O(n log n) = O(1,000 × 10) ≈ 10,000. Похоже; сортировка может быть проще.

Обмен время-память

Сортировка использует O(n) память (или O(1) с трюками на месте). Топ-K использует O(k) память. Когда k намного меньше чем n, куча экономит память.

Практика 0 / 6

Чтобы найти k наибольших элементов, должен ли ты использовать мин-кучу или макс-кучу размера k?

Что такое k-й по величине элемент в контексте алгоритма топ-K кучи?

Дан arr = [3, 2, 1, 5, 6, 4] и k = 2, что такое k-й по величине элемент?

Какая сложность времени нахождения k наибольших элементов используя мин-кучу?

Ты хочешь найти 5 наибольших элементов в массиве 1,000,000 чисел. Примерно сколько больше операций берёт сортировка сравнительно с подходом кучи? (Используй log₂(1,000,000) ≈ 20 и log₂(5) ≈ 2.3.)

Проблема «топ k по частоте» просит: дан массив, найди k самых частых элементов. Как бы ты применил стратегию кучи?

lesson.inset.undefined

Почему топ-K имеет значение. Реальные системы часто просят: дай мне топ 10 результаты поиска, или топ 100 пользователей по вовлечённости, или топ k редчайшие ошибки. Сортировка всего датасета каждый раз это трата. Топ-K куча позволяет тебе ответить на эти запросы эффективно, даже на большие датасеты и потоки. Стриминг кейс: представь датчик непрерывно выпускает показания. Ты хочешь знать 100 наибольших показаний видимых до сих пор. Ты не можешь хранить все показания (памятью ограниченный). Куча размера-100 позволяет тебе держать топ 100 онлайн, обрабатывая каждое показание в O(log 100) времени.

lesson.inset.undefined

Используя макс-кучу вместо мин-кучи. Если держишь макс-кучу размера k чтобы найти k наибольших, наибольший элемент в корне — но ты хочешь выкинуть наименьшего кандидата когда куча превышает k. Макс-куча заставляет тебя искать всю кучу на минимум, что O(k), не O(log k). Мин-куча держит наименьшего кандидата (выкидываемого) в корне, так одно сравнение говорит тебе если новый элемент принадлежит топ k.

lesson.inset.undefined

k равен n или k больше чем n. Если k ≥ n, каждый элемент в топ k, так просто верни весь массив. Если k = 0, верни пустой список. Если k это 1, ты находишь одинарный максимум, что O(n) с кучей (один проход, один insert за элемент, размер никогда не превышает 1) или O(n) с линейным сканированием.

Проверь себя

Викторина

Объясни алгоритм топ-K кучи. Почему ты используешь мин-кучу размера k вместо макс-кучи или сортировки?

Итог

Чтобы найти k наибольших элементов, держи мин-кучу размера k. Для каждого элемента в массиве, добавь его и выкидывай минимум когда куча превышает k. Финальная куча содержит ровно k наибольших, и её корень это k-й по величине элемент. Время: O(n log k). Память: O(k). Это бьёт сортировку (O(n log n)) когда k ≪ n. Симметричная логика применяется к k наименьшим (используй макс-кучу). Одинаковый паттерн решает «топ k по частоте»: посчитай частоты, применить стратегию кучи на значения частоты. Следующее: урок 05 расширяет это в k-way merge, где ты держишь размера-k кучу потоков, вытягивая следующий минимум из потока чей головой минимум.

Продолжить восхождение ↑K-путевое слияние и слияние отсортированных списков