ヒープの基本格納

一、概念とその紹介

ヒープ(Heap)は、コンピュータサイエンスにおける特殊なデータ構造の総称です。

ヒープは通常、完全二分木とみなすことができる配列オブジェクトです。

ヒープは次の性質を満たします:

  • ヒープ内のあるノードの値は、常にその親ノードの値以下であるか、または常にその親ノードの値以上です。
  • ヒープは常に完全二分木です。

二、適用の説明

ヒープは完全二分木の構造を利用してデータの集合を管理し、関連する操作を行います。一般的な操作の1回の時間計算量は、O(1)~O(logn)の間にあり、ヒープは通常、プログラムが使用するオブジェクトの動的割り当てと解放に使用されます。

優先キューの使用シーンでは、通常の配列または順序配列の場合、最悪のケースはO(n^2)ですが、ヒープというデータ構造を使用すると、エンキューとデキューの効率も向上させることができます。

 エンキューデキュー
通常の配列O(1)O(n)
順序配列O(n)O(1)
堆O(logn)O(log)

三、構造図

二分ヒープは完全二分木であり、ヒープ内のノードの値は常に親ノードの値以下です。この完全二分木の深さは k で、第 k 層を除く各層(1〜k-1)のノード数はすべて最大数に達し、第 k 層のすべてのノードは左端に連続して集まっています。

そのうち、ヒープのルートノードが最大であるものを最大ヒープと呼び、次の図のようになります:

配列を使用して二分ヒープを格納できます。右側の番号は配列のインデックスです。

現在の要素のインデックス位置が i であると仮定すると、次の規則が得られます:

parent(i) = i/2(取整)
left child(i) = 2*i
right child(i) = 2*i +1

四、Java サンプルコード

ソースコードパッケージのダウンロード:Download

src/サンプル/heap/MaxHeap.java ファイルコード:

package サンプル.heap;

/**
* ヒープ定義
 */

public class MaxHeap<T> {
    private T[] data;
    private int count;
    // コンストラクタ。capacity個の要素を格納できる空のヒープを構築します
    public MaxHeap(int capacity){
        data = (T[])new Object[capacity+1];
        count = 0;
    }
    // ヒープ内の要素数を返します
    public int size(){
        return count;
    }
    // ヒープが空かどうかを示すブール値を返します
    public boolean isEmpty(){
        return count == 0;
    }
    // MaxHeap のテスト
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
        System.out.println(maxHeap.size());
    }
}
その他の拡張