Существует много сценариев применения структуры данных кучи, и самый классический из них — сортировка кучей. Heapsort — это алгоритм сортировки на месте с временной сложностью O(nlogn). Сегодня мы разберем структуру данных кучи.
1. Что такое куча
Куча — это особый вид дерева. Пока выполняются следующие два пункта, это называется кучей.
- Куча — это полное бинарное дерево.
- Значение каждого узла кучи должно быть больше или равно (или меньше или равно) значению каждого узла в его поддереве.
Для кучи, в которой значение каждого узла больше или равно значению каждого узла в его поддереве, мы называем ее «кучей с большой вершиной». Для кучи, в которой значение каждого узла меньше или равно значению каждого узла в его поддереве, мы называем ее «маленькой верхней кучей».
2. Как реализовать кучу
Сначала нам нужно знать, какие операции поддерживает куча и как хранить кучу.
Для полного бинарного дерева использование массива для его хранения очень эффективно использует память. Поскольку нам не нужно хранить указатели на левый и правый дочерние узлы, мы можем найти левый и правый дочерние узлы и родительские узлы узла, просто подписав массив. Как показано ниже.
Как показано на рисунке, узел с индексом i в массиве имеет индекс 2 своего левого дочернего узла.i, его правый потомок имеет индекс 2i+1, индекс его родительского узла равен i/2. Давайте взглянем на общие операции с кучей. Возьмем в качестве примера кучу с большим верхом и посмотрим на операции вставки и удаления в куче.
1. Вставить элемент в кучу
После вставки нового элемента в кучу нам нужно продолжать удовлетворять два свойства кучи.
Если мы поместим вновь вставленный элемент в конец кучи, он не будет соответствовать характеристикам кучи, поэтому нам нужно настроить его так, чтобы он соответствовал характеристикам кучи. Регулировка делится на регулировку вверх и регулировку вниз. В качестве примера возьмем регулировку вверх. Как показано ниже.
Этот процесс очень прост, мы позволяем вновь вставленному узлу сравнить размер своего родительского узла. Если он не удовлетворен тем, что дочерний узел меньше или равен родительскому узлу, мы обмениваем два узла. Этот процесс повторяется до тех пор, пока требования не будут выполнены.
2. Удалить верхний элемент кучи
Далее рассмотрим операцию удаления. Сначала мы меняем местами последний элемент кучи с верхним элементом, а затем удаляем последний элемент. Остальные элементы кучи не соответствуют требованиям кучи.Нам нужно настраивать от вершины кучи к низу, пока родительский и дочерний узлы не будут соответствовать соотношению размеров. Как показано ниже.
Мы знаем, что полное бинарное дерево, содержащее n узлов, высота дерева не будет превышать log2n, процесс настройки кучи заключается в сравнении и обмене по пути, где расположены узлы, поэтому временная сложность пропорциональна высоте куча, которая равна O (logN). Основной логикой вставки данных и удаления верхних данных кучи является корректировка кучи, поэтому временная сложность вставки элемента в кучу и удаления верхнего элемента кучи составляет O(logN).
3. Куча сортировки
В прошлый раз мы говорили о многих методах сортировки, вы можете нажатьАлгоритм сортировкичтобы проверить это. Сегодня мы продолжаем говорить о новом алгоритме сортировки — куче, который имеет временную сложность O(nlogN) и является алгоритмом сортировки на месте. Мы можем грубо разделить процесс сортировки кучи на два основных этапа, а именно создание кучи и сортировку.
1. Создайте кучу
Сначала мы создаем кучу вместо массива. «На месте» означает работу с исходным массивом без обращения к другому массиву. Наша идея реализации состоит в том, чтобы обрабатывать данные сзади наперед, и все данные корректируются сверху вниз.
Давайте рассмотрим следующие шаги декомпозиции для построения кучи. Поскольку корректировку листовых узлов вниз можно сравнивать только с ними самими, мы можем начать непосредственно с последнего нелистового узла и по очереди корректировать вниз.
Как показано на рисунке, мы корректируем данные с нижними индексами от n/2 до 1. Узлы с индексами от n/2+1 до n являются листовыми узлами, поэтому нам не нужно настраивать. \
2. Сортировать
После создания кучи данные в массиве упорядочены в соответствии с характеристиками большой верхней кучи. Первый элемент массива — это вершина кучи, которая является самым большим элементом. Мы меняем его местами с последним элементом, и самый большой элемент помещается в индекс n.
Этот процесс аналогичен операции удаления вершины кучи.Когда верхний элемент кучи удаляется, мы помещаем элемент с индексом n на вершину кучи, а затем корректируем его вниз, чтобы перестроить оставшиеся n- 1 элемент в кучу. После того, как настройка завершена, мы берем верхний элемент кучи и помещаем его в позицию с нижним индексом n-1, и повторяем этот процесс, пока в куче не останется только один элемент с нижним индексом 1, и работа сортировки выполнен.
Теперь давайте проанализируем временную сложность, пространственную сложность и стабильность сортировки кучи. Во всем процессе сортировки кучи требуется только отдельное пространство для временного хранения, поэтому сортировка кучи — это алгоритм сортировки на месте. Сортировка кучи включает в себя две операции: создание кучи и сортировка, временная сложность построения кучи составляет O(n), а временная сложность процесса сортировки — O(nlogN). Таким образом, общая временная сложность сортировки кучей составляет O(nlogN). Поскольку в процессе сортировки происходит операция обмена последним узлом кучи с вершиной кучи, поэтому можно изменить исходный относительный порядок данных с тем же значением, поэтому сортировка кучей не является стабильной. алгоритм сортировки.
В-четвертых, применение кучи
Давайте поговорим о нескольких очень важных приложениях кучи.
1. Приоритетная очередь
Очередь с приоритетом, как следует из названия, — это прежде всего очередь. Самая большая особенность очереди - первый вошел, первый вышел. Однако в приоритетной очереди порядок удаления из очереди не в соответствии с принципом «первым пришел — первым вышел», а в соответствии с приоритетом, и тот, у кого более высокий приоритет, будет исключен из очереди первым.
Как реализовать приоритетную очередь? На самом деле существует много способов, но использование кучи является наиболее простым и эффективным. Потому что кучи и приоритетные очереди очень похожи. Куча может рассматриваться как приоритетная очередь. Вставка элемента в приоритетную очередь эквивалентна вставке элемента в кучу; удаление элемента с наивысшим приоритетом из приоритетной очереди эквивалентно удалению верхнего элемента кучи. Рассмотрим следующий сценарий приложения.
Предположим, у нас есть 100 небольших файлов, каждый из которых имеет размер 100 МБ. В каждом файле хранятся упорядоченные строки. Мы хотим объединить эти маленькие файлы в один упорядоченный большой файл. Здесь используются приоритетные очереди. Мы возьмем строку из каждого из 100 маленьких файлов, а затем построим небольшую верхнюю кучу.Элемент в верхней части кучи — это первый элемент приоритетной очереди, которая является наименьшей строкой. Мы помещаем эту строку в большой файл и удаляем ее из кучи. Затем возьмите следующую строку из маленького файла и поместите ее в кучу. Повторяя этот процесс, данные 100 маленьких файлов можно по очереди помещать в большой файл.
2. Используйте кучу, чтобы найти topK
Мы можем разделить проблему поиска топк на две категории. Один тип предназначен для статических наборов данных, то есть наборы данных определяются заранее и не изменяются. Другой тип предназначен для динамических наборов данных, то есть набор данных заранее не определен, и данные добавляются к набору динамически. Для статических наборов данных, как найти верхние K больших данных в массиве, содержащем n данных?Мы можем поддерживать маленькую верхнюю кучу размера k, последовательно проходить массив, брать данные из массива и сравнивать верхние элементы кучи. Если он больше верхнего элемента кучи, мы удаляем верхний элемент кучи и вставляем этот элемент в кучу, если он меньше верхнего элемента кучи, мы его не обрабатываем и продолжаем обход множество. Таким образом, после того, как данные в массиве пройдены, данные в куче являются первыми K большими данными. Найдите topK для динамических данных, то есть topK в реальном времени. Как понять это? Я привожу пример. В наборе данных есть две операции: одна — добавить данные, а другая — запросить текущие K больших данных. Если мы будем пересчитывать на основе текущих данных каждый раз, когда запрашиваем k лучших больших данных, то временная сложность составит O (nlogN), где n представляет размер текущих данных. На самом деле мы всегда можем поддерживать небольшую верхнюю кучу размером k, и когда есть данные, которые нужно добавить в коллекцию, мы сравниваем их с верхним элементом кучи. Если он больше верхнего элемента кучи, мы удаляем верхний элемент кучи и вставляем этот элемент в кучу, если он меньше верхнего элемента кучи, мы его не обрабатываем. Таким образом, всякий раз, когда нам нужно запросить K больших данных, мы можем немедленно вернуть их.
Для получения более глубоких знаний, пожалуйста, обратите внимание на общедоступный номер "Программист старший".