data-structures
バイナリヒープ
サーチ…
前書き
バイナリヒープは、ヒープ順序付けプロパティを満たす完全なバイナリツリーです。最小ヒーププロパティ:各ノードの値は親の値以上で、最小値の要素はルートにあります。
例
ミニヒープ
1
/ \
2 3
/ \ / \
4 5 6 7
上記のツリーは、ツリー内に存在するすべてのノードの中でルートが最小であるため、Min-Heapです。同じプロパティの後ろに、ツリー内のすべてのノードがあります。
最大ヒープ
7
/ \
6 5
/ \ / \
4 3 2 1
上記のツリーは、ツリー内に存在するすべてのノードの中でルートが最大であるため、最大ヒープです。ツリー内のすべてのノードが同じプロパティの後に続きます。
Min-Heapでサポートされる操作
getMin() - ルート要素を返します。配列の最初の要素であるため、
O(1)
最小要素を取得できます。extractMin() - ヒープから最小要素を削除します。要素を削除した後、ツリーはMin-Heapプロパティを満たす必要があり、ツリープロパティを維持するために操作( ヒープ化 )が実行されます。これは
O(logn)
dereaseKey() - キーの値を減らします。この操作の複雑さは
O(logn)
insert() - キーは常にツリーの最後に挿入されます。追加されたキーがheapプロパティに従わない場合、ツリーがヒーププロパティを満たすようにする必要があります。このステップでは、
O(logn)
時間。delete() - このステップは
O(logn)
時間がかかります。鍵を削除するには、まず鍵の値を最小値に減らしてからこの最小値を抽出する必要があります。
ヒープの適用
- ヒープソート
- 優先度キュー
HeapはDijkstra's Shortest Path
やPrim's Minimum Spanning Tree
などDijkstra's Shortest Path
グラフアルゴリズムの多くで使用されています。
Javaでの実装
public class MinHeap {
int hArr[];
int capacity;
int heapSize;
public MinHeap(int capacity){
this.heapSize = 0;
this.capacity = capacity;
hArr = new int[capacity];
}
public int getparent(int i){
return (i-1)/2;
}
public int getLeftChild(int i){
return 2*i+1;
}
public int getRightChild(int i){
return 2*i+2;
}
public void insertKey(int k){
if(heapSize==capacity)
return;
heapSize++;
int i = heapSize-1;
hArr[i] = k;
while(i!=0 && hArr[getparent(i)]>hArr[i]){
swap(hArr[i],hArr[getparent(i)]);
i = getparent(i);
}
}
public int extractMin(){
if(heapSize==0)
return Integer.MAX_VALUE;
if(heapSize==1){
heapSize--;
return hArr[0];
}
int root = hArr[0];
hArr[0] = hArr[heapSize-1];
heapSize--;
MinHeapify(0);
return root;
}
public void decreaseKey(int i , int newVal){
hArr[i] = newVal;
while(i!=0 && hArr[getparent(i)]>hArr[i]){
swap(hArr[i],hArr[getparent(i)]);
i = getparent(i);
}
}
public void deleteKey(int i){
decreaseKey(i, Integer.MIN_VALUE);
extractMin();
}
public void MinHeapify(int i){
int l = getLeftChild(i);
int r = getRightChild(i);
int smallest = i;
if(l<heapSize && hArr[l] < hArr[i])
smallest = l;
if(l<heapSize && hArr[r] < hArr[smallest])
smallest = r;
if(smallest!=i){
swap(hArr[i], hArr[smallest]);
MinHeapify(smallest);
}
}
public void swap(int x, int y){
int temp = hArr[x];
hArr[x] = hArr[y];
hArr[y] = temp;
}
}