ヒープ
Outline
ヒープとは、完全二分木(Complete Binary Tree)の特殊なものとして考えることができる.
ヒープの特徴は、任意の節点についてその節点のもつ値がその節点の親のもつ値よりも小さいことである.
ヒープは基本的なデータ構造の一つであるが、その応用として、
幅広い分野で用いられているPriority Queue?がある.
Program
ヒープを実現するクラス.
ヒープソート用関数を含める.
class Heap {
private:
int heap[_HEAP_MAX];
int n; // 配列heapのサイズ
int size; // 配列heap中のヒープ要素のサイズ
public:
int parent(int i) {
if(i == 0) {
return -1;
}
return i / 2;
}
int left(int i) {
if(2 * i >= size) {
return -1;
}
return 2 * i;
}
int right(int i) {
if(2 * i + 1 >= size) {
return -1;
}
return 2 * i + 1;
}
// ヒープ条件を保持する
void heapify(int i) {
int m = i; // max element index
int l = left(i);
int r = right(i);
if(l != -1) {
m = (heap[l] > heap[i]) ? l : i;
}
if(r != -1) {
m = (heap[m] > heap[r]) ? m : r;
}
if(m != i) {
swap(heap[i], heap[m]);
heapify(m);
}
}
void build_heap(int data[], int nn) {
copy(data, data + nn, heap);
n = size = nn;
for(int i = (size / 2) - 1 ; i >= 0 ; i--) {
heapify(i);
}
}
void swap_elem(int i, int j) {
swap(heap[i], heap[j]);
}
void decrement_size() {
size--;
}
void copy_array(int data[]) {
copy(heap, heap + n, data);
}
};