Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
C++ source code to generate a heap with the downward method.
/***********************************************************
* ヒープ生成(下方移動)
**********************************************************/
#include <cstdlib> // for srand()
#include <iostream> // for cout
#include <stdio.h> // for printf()
#define N 100 // データ個数
using namespace std;
/*
* ヒープクラス
*/
class Heap
{
// 各種変数
int n, i, s, p, w; // Loop インデックス等
int heap[N + 1]; // 木(後のヒープ)用配列
public:
Heap(); // コンストラクタ
void generate(); // ヒープ生成
private:
void swap(int *, int *); // 要素交換
};
/*
* コンストラクタ
*/
Heap::Heap()
{
// ヒープの元になる木を生成
srand((unsigned int)time(NULL));
printf("#### Tree\n");
for (i = 1; i <= N; i++) {
heap[i] = rand() % N + 1;
printf("%5d ", heap[i]);
if (i % 10 == 0) printf("\n");
}
printf("\n");
}
/*
* ヒープ生成
*/
void Heap::generate()
{
n = N; // データ個数
for (i = n / 2; i >= 1; i--) {
p = i; // 親要素の位置
s = 2 * p; // 左の子要素の位置
while (s <= n) {
if (s < n && heap[s + 1] < heap[s]) s++; // 左右子要素の小さい方
if (heap[p] <= heap[s]) break;
swap(&heap[p], &heap[s]);
p = s; // 親要素の位置
s = 2 * p; // 左の子要素の位置
}
}
// 結果出力
printf("#### Heap\n");
for (i = 1; i <= n; i++) {
printf("%5d ", heap[i]);
if (i % 10 == 0) printf("\n");
}
printf("\n");
}
void Heap::swap(int *a, int *b)
{
w = *a;
*a = *b;
*b = w;
}
/*
* メイン処理
*/
int main()
{
try
{
// ==== インスタンス化
Heap objHeap;
// ==== ヒープ生成
objHeap.generate();
}
catch (...) {
// ==== 異常終了
cout << "例外発生!" << endl;
return -1;
}
// ==== 正常終了
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.