Куча — это структура данных, которая следует определенному набору правил для поддержания определенного порядка среди ее элементов. Кучи обычно используются в различных алгоритмах, включая сортировку и приоритетные очереди. В этом руководстве мы реализуем кучу в Swift и обсудим основные принципы ее работы.

Выполнение

Для начала нам нужно создать класс, который будет представлять нашу кучу. Мы начнем с объявления простой структуры для хранения наших элементов:

struct Heap<T> {
    var elements: [T]
}

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

Чтобы обеспечить соблюдение этого правила, мы определим функцию, которая сравнивает два элемента и возвращает true, если первый элемент меньше второго:

struct Heap<T> {
    var elements: [T]
    
    func isLessThan(_ a: T, _ b: T) -> Bool {
        // Add code to compare a and b and return true if a is less than b
    }
}

Далее мы определим функцию для добавления элемента в нашу кучу. Эта функция вставит элемент в конец кучи, а затем переупорядочит элементы, чтобы сохранить свойство кучи.

Чтобы сделать это, мы будем использовать процесс, называемый «пузырьком». Мы начинаем с вновь вставленного элемента и сравниваем его с его родителем. Если он меньше своего родителя, мы меняем два элемента местами. Затем мы продолжаем этот процесс, пока не достигнем корня кучи или пока элемент не станет меньше своего родителя.

Вот код функции add:

struct Heap<T> {
    var elements: [T]
    
    func isLessThan(_ a: T, _ b: T) -> Bool {
        // Add code to compare a and b and return true if a is less than b
    }
    
    mutating func add(_ element: T) {
        elements.append(element)
        
        var currentIndex = elements.count - 1
        while currentIndex > 0 {
            let parentIndex = (currentIndex - 1) / 2
            if isLessThan(elements[currentIndex], elements[parentIndex]) {
                elements.swapAt(currentIndex, parentIndex)
                currentIndex = parentIndex
            } else {
                break
            }
        }
    }
}

Теперь, когда мы можем добавлять элементы в нашу кучу, давайте реализуем функцию для удаления минимального элемента. Эта функция удалит корневой элемент и заменит его последним элементом в куче. Затем мы переставим элементы, чтобы сохранить свойство кучи.

Для этого мы будем использовать процесс под названием «погружение». Мы начинаем с корневого элемента и сравниваем его с его дочерними элементами. Если он больше, чем один из его дочерних элементов, мы меняем его местами с меньшим дочерним элементом. Затем мы продолжаем этот процесс до тех пор, пока элемент не станет больше, чем один из его дочерних элементов.

Вот код функции removeMin:

struct Heap<T> {
    var elements: [T]
    func isLessThan(_ a: T, _ b: T) -> Bool {
        // Add code to compare a and b and return true if a is less than b
    }

    mutating func add(_ element: T) {
        elements.append(element)
    
        var currentIndex = elements.count - 1
        while currentIndex > 0 {
            let parentIndex = (currentIndex - 1) / 2
            if isLessThan(elements[currentIndex], elements[parentIndex]) {
                elements.swapAt(currentIndex, parentIndex)
                currentIndex = parentIndex
            } else {
                break
            }
        }
    }

    mutating func removeMin() -> T? {
        guard elements.count > 0 else {
            return nil
        }
    
        if elements.count == 1 {
            return elements.removeFirst()
        }
    
        let min = elements[0]
        elements[0] = elements.removeLast()
    
        var currentIndex = 0
        while currentIndex < elements.count {
            let leftChildIndex = currentIndex * 2 + 1
            let rightChildIndex = currentIndex * 2 + 2
        
            var minChildIndex: Int
            if rightChildIndex < elements.count {
                minChildIndex = isLessThan(elements[leftChildIndex], elements[rightChildIndex]) ? leftChildIndex : rightChildIndex
            } else if leftChildIndex < elements.count {
                minChildIndex = leftChildIndex
            } else {
                break
            }
        
            if isLessThan(elements[minChildIndex], elements[currentIndex]) {
                elements.swapAt(minChildIndex, currentIndex)
                currentIndex = minChildIndex
            } else {
                break
            }
        }
    
        return min
    }
}

Заключение

В этом уроке мы узнали, как реализовать мини-кучу в Swift. Мы обсудили основные принципы работы кучи и реализовали функции для добавления и удаления элементов из кучи.

Если вы хотите узнать больше о кучах, вы можете обратиться к следующим ресурсам:

Я надеюсь, что это руководство помогло вам понять, как реализовать и использовать кучу в ваших собственных проектах. Удачного кодирования