[iOS CS Studio]優先キュー

21.06.26
これは学習内容を整理するための文章で、完全に正確ではないかもしれません.
参考までに、内容が足りないと思ったら、他の文章を読むこともできます.
+間違った部分、修正が必要な部分は、いつでもフィードバックしてください.😊
                                                 by. ryalya
入る前に.
前回の記事では、スタックとキューからQについて簡単に理解しました.
簡単に再定義すると、Queueは以下のようになります.
最初の入力/出力=入力/出力
入れ順に出る(先進的なデータ先進)
リンクリストのインプリメンテーション.
 -典型的な例は、銀行ウィンドウキューです.
 -入り口と出口が分かれていると思えば簡単です.

Priority Queueとは?

前述したようにQueueはFIFO形式の資料構造である.
ただし、優先順位キュー(Priority Queue、優先順位キュー)は、入る順番に関係なく優先順位の高いデータが先に表示されます.

一般的なQueueは、次のような線形構造を有する。

ただし、Priority Queueの構造は以下のようにツリー構造と見なすべきである。

データ構造スタックでは、heapは優先キューのために作成されたデータ構造である.
これは、優先キューがheapというデータ構造によって実現できるためである.
しかし,優先キューを配列やリンクリストで実現できる以上,なぜhipで実現するのか.
ChanBLOGで見た内容は地理的によく理解され、そのまま持ってきた.😊

配列/リンクリストを使用して優先キューを実装しないのはなぜですか?

整列

配列の先頭から優先度の高い順に入れると、先頭のインデックスを直接使用すればよいので、優先度の高いデータを返すのは難しくありません.
しかし,優先順位が中間の挿入過程では,後続のデータまでインデックスを1つ後ろに押すという欠点がある.
最悪の場合、すべてのインデックスを参照して、挿入する場所を検索する必要があります.
すなわち,データがnの場合,時間的複雑度はO(n)である.
→アレイ別実施時の時間的複雑度:削除はO(1)、挿入はO(n)

リンクリスト

優先度の高い順序で接続すると、優先度の高いデータを返すのは配列と同じように簡単です.
ただし、接続リストの挿入プロセスは配列と同様に、その位置を見つける必要があります.
最悪の場合、行き止まりになります.
→接続リストを実施する際の時間的複雑度:削除はO(1)、挿入はO(n)

¥¥¥

hipの場合、削除または挿入中に親と子の比較のみが行われます.
バイナリツリーの高さを1つ増加するごとに、格納可能なデータは2倍に増加し、比較演算回数は1回増加します.
すなわち,削除や挿入が最悪であれば,O(log 2 n)の時間的複雑さがある.
→接続リストで実現する場合の時間的複雑度:O(log 2 n)に削除し、O(log 2 n)に挿入する
このように、配列や接続リストが削除時に時間的複雑度の優位を占めていても、挿入する時間的複雑度はお尻に基づいているので、ずれの大きい配列や接続リストよりもお尻を使って実現!!
データ構造優先キューとhipによる時間的複雑さをまとめた表です.

優先順位キューの実装

Priority Queueの演算はheapを利用しているのでheapと同じと考えられる.
新しいノードを追加するときは,最末端から追加し,自分の親のインデックス(index-1)/2と比較し,逆に上昇し,hip条件に合致するか否かを比較し,条件に合致するまで親と子の位置を置き換える.
上(ルート)ノードも削除し、最後のノードをルートとして挿入し、ヒップ条件を下に比較し、親ノードと子ノードの位置を条件に一致するまで置き換えます.
SWIFTを使用して優先キューを実装するコードは、次のとおりです.
優先キュー優先キューから持ってきました.

Heap実施

struct Heap<T: Comparable> {
    var nodes: [T] = []
    let sort: (T,T) -> Bool
    
    init(sort: @escaping (T,T) -> Bool) {
        self.sort = sort
    }

insert (push)

    // Heap에 데이터 추가 (push)
    mutating func insert(_ element: T) {
        let count = nodes.count
        nodes.append(element)
        
        up(count - 1)
    }

delete (pop)

    // Heap에서 데이터 꺼내면서 삭제 (pop)
    mutating func delete() -> T? {
        if nodes.isEmpty {
            return nil
        }
        if nodes.count == 1 {
            return nodes.removeFirst()
        }
        nodes.swapAt(0, nodes.count - 1)
        
        let result = nodes.removeLast()
        down(0)
        
        return result
    }
    
    // Heap에서 특정 데이터 삭제
    mutating func remove(_ element: T) {
        if let index = nodes.firstIndex(of: element) {
            nodes.swapAt(index, nodes.count - 1)
            nodes.removeLast()
            up(index)
            down(index)
        }
    }
    
    // Heap에서 데이터 전체 삭제
    mutating func removeAll(_ element: T) {
        var count = nodes.count
        remove(element)
        while nodes.count < count {
            remove(element)
            count = nodes.count
        }
    }
    
    // Heap에서 첫 데이터 pop
    func peek() -> T? {
        return nodes.first
    }

データのソート

    // Heap 데이터 아래방향으로 비교 정렬
    mutating func down(_ index: Int) {
        var index = index
        let count = nodes.count
        while 2 * index + 1 < count {
            var i = 2 * index + 1
            if i < (count - 1) && sort(nodes[i], nodes[i + 1]) {
                i += 1
            }
            if !sort(nodes[index], nodes[i]) {
                break
            }
            nodes.swapAt(index, i)
            index = i
        }
    }
    
    // Heap 데이터 윗방향으로 비교 정렬
    mutating func up(_ index: Int) {
        var index = index
        while index > 0 && !sort(nodes[(index - 1)], nodes[index]) {
            nodes.swapAt((index - 1) / 2, index)
            index = (index - 1) / 2
        }
    }
}

結果値

var queue: Heap<Int> = Heap<Int>() {
    return $0 > $1
}
queue.insert(3)
queue.insert(5)
queue.insert(2)
queue.insert(1)
queue.insert(6)
queue.insert(7)
queue.insert(4)
// nodes: [7, 5, 6, 1, 3, 2, 4] -- 결과값

サンプルコードによる実装は難しくないことを理解した.
しかしSweetでは配列で表現する方が効率的ですか?私はこのような話を見ましたが、これはどういう意味ですか?

Reference

配列/リンクリストを使用して優先キューを実装しない理由:ChanBLOG
時間複雑度テーブル:データ構造優先キューとhip
Priority Queue実施:優先キュー優先キュー