2.実戦講座

Heapは、親ノードと子ノードの間に一定のサイズ関係を持つ完全なバイナリツリーである優先キューのデータ構造です.データ全体をソートするのではなく、いくつかの最大値が必要な場合は、B型試験で一般的なデータ構造であるため、これらの値を使用することが多いので、詳細に理解し、必要に応じて迅速に実施することをお勧めします.

2.1. アレイによるHeapの実装

Heapは完全なバイナリツリーであるため、配列で実装する場合、次の簡単な式を使用して親ノードと子ノードにアクセスできます.

[Rootノードのインデックスが0で始まる場合]

•親インデックス=(子インデックス-1)/2
•左サブインデックス=(親インデックス)*2+1
•右子索引=(親索引)*2+2

[Rootノードのインデックスが1で始まる場合]

•親インデックス=(子インデックス)/2
•左側の子索引=(親索引)*2
•右サブインデックス=(親インデックス)*2+1
「heap」の「挿入」(push)は、最悪の場合、LeafノードからRootノードまでのすべての値を比較するので、時間的複雑さはツリーの高さO(log 2 N)となる.同様に、「heapを削除」(pop)もO(log 2 N)であり、最悪の場合、ルーティングノードからLeafノードまでのすべての値を比較するためである.
Heapの原則はアレイによって実施され、以下の例に示す.これは,新しいノードを接続リストとして実装すると,最後の位置に追加することが困難になるためである.したがって,実行速度では,接続リストよりもO(1)の時間的複雑さで最後の位置の配列に直接アクセスできる方が効率的である.
次に、配列を使用して実装される最小heapのコードの例を示します.
Heapインデックスは0から始まります.

#include < stdio.h >
#include < stdlib.h >
#define MAX_SIZE 100

int heap[MAX_SIZE];
int heapSize = 0;

void heapInit(void) {
	heapSize = 0;
}

int heapPush(int value) {
if (heapSize + 1 > MAX_SIZE) {
		printf("queue is full!");
return 0;
	}

	heap[heapSize] = value;// 마지막 노드에 값 추가// 마지막 노드에 추가한 값을 올바른 위치로 옮긴다int current = heapSize;
while (current > 0 && heap[current] < heap[(current - 1) / 2]) {// 부모와 자식의 우선순위 비교// 자식의 우선순위가 더 높으면 부모와 값을 바꿔준다int temp = heap[(current - 1) / 2];
		heap[(current - 1) / 2] = heap[current];
		heap[current] = temp;
		current = (current - 1) / 2;
	}

	heapSize = heapSize + 1;
return 1;
}

int heapPop() {
if (heapSize <= 0)
return -1;

int value = heap[0];
	heapSize = heapSize - 1;
	heap[0] = heap[heapSize];// 마지막 data를 root에 저장// root에 저장된 값을 올바른 위치로 옮긴다int current = 0;
while (current * 2 + 1 < heapSize) {
int child;
if (current * 2 + 2 == heapSize)
			child = current * 2 + 1;
else
			child = heap[current * 2 + 1] < heap[current * 2 + 2] ? current * 2 + 1 : current * 2 + 2;

if (heap[current] < heap[child])
break;

int temp = heap[current];
		heap[current] = heap[child];
		heap[child] = temp;
		current = child;
	}
return value;
}

void main() {
	srand(11);
	heapInit();

for (int i = 0; i < 100; i++)
		heapPush(rand() % 100);

for (int i = 0; i < 100; i++)
		printf("%d ", heapPop());
	printf("\n");
}

2.2. 接続リストを使用したHeapの実装

ただし、拡大しにくいアレイの特性上、最大スタックサイズのアレイを事前に割り当てて使用すると、メモリ領域に関連する問題が発生する場合があります.
たとえば、アルゴリズムの問題を解くとき、次のように仮定します.

1000人のユーザーが存在します.

ユーザーにデータを割り当てる.

各ユーザは、割り当てられたデータを自分のHeapで管理する.(例えば、各ユーザは、優先度の高いデータをいつでも10個返す必要がある)

データ配分は最大10万回実施する.

この場合、各ユーザは、ユーザが100000個のデータを持つ可能性があるため、最大heapサイズ100000の配列を作成する必要があります.このときuserは1000であるため,配列の総サイズは1000 x 1000000である.これにより、アレイが大きすぎてメモリ領域の問題が発生する可能性があります.
メモリ領域の問題を解決するには、次のリンクリストに基づくheapを考慮します.
heapインデックスは1から始まります.

#include < stdio.h >
#include < stdlib.h >

#define MAXN 1000
#define MAXNODE 1000000
#define NULL (0)

typedef struct HeapNode {
	struct HeapNode *parent, *child[2];
	int value;
};

int heapNodePoolCnt;
HeapNode heapNodePool[MAXNODE];

typedefstruct Heap {
	HeapNode* root;
int size;

void init() {
		size = 0;
	}

	HeapNode* create() {
		HeapNode* node = &heapNodePool[heapNodePoolCnt++];// 메모리 풀에서 가져옴
		node->parent = node->child[0] = node->child[1] = NULL;
return node;
	}

	HeapNode* findNode(int ind) {
if (ind == 1)return root;
elsereturn findNode(ind >> 1)->child[ind & 1];
	}

void push(int value) {
if (size + 1 > MAXNODE) {
			printf("queue is full!\n");
return;
		}

		HeapNode* cur = create();// 새로운 노드 생성
		cur->value = value;
if (size == 0) {// data가 없으면
			root = cur;// 새로운 노드가 root 노드가 된다
			size++;
return;
		}
else {
			size++;
			HeapNode* par = findNode(size >> 1);// 부모를 찾는다
			par->child[size & 1] = cur;// 찾은 부모와 새로 생성한 노드를 부모-자식 관계로 연결한다
			cur->parent = par;
while (cur != root && cur->value < cur->parent->value) {// 추가한 자식과 부모의 우선순위 비교// 자식의 우선순위가 더 높으면 부모와 값을 바꿔준다int temp = cur->value;
				cur->value = cur->parent->value;
				cur->parent->value = temp;
				cur = cur->parent;
			}
		}
	}

int pop() {
if (size <= 0) {
			printf("queue is empty!\n");
return -1;
		}
elseif (size == 1) {// data가 하나이면, 그 값을 리턴
			size = 0;
return root->value;
		}

int value = root->value;
		HeapNode* cur = findNode(size);// heap의 마지막 노드를 찾는다
		root->value = cur->value;// 마지막 노드의 값을 root에 저장
		cur->parent->child[size & 1] = NULL;// 마지막 노드 제거
		size--;

// root에 저장된 값을 올바른 위치로 옮긴다
		cur = root;
while (cur->child[0] != NULL) {
			HeapNode* child;
if (cur->child[1] == NULL)
				child = cur->child[0];
else
				child = cur->child[0]->value < cur->child[1]->value ? cur->child[0] : cur->child[1];

if (cur->value < child->value)
break;

int temp = child->value;
			child->value = cur->value;
			cur->value = temp;
			cur = child;
		}

return value;
	}
};

Heap heap[MAXN];

void main() {
	srand(11);
	heapNodePoolCnt = 0;
for (int i = 0; i < MAXN; i++)
		heap[i].init();

for (int i = 0; i < MAXNODE; i++) {// 총 1,000,000 data 할당int ind = rand() % MAXN;
		heap[ind].push(rand() % MAXNODE);
	}

for (int i = 0; i < MAXN; i++) {
		printf("heap[%d]: ", i);
for (int j = 0; j < 10; j++)// 우선순위가 높은 data 10 개 출력printf(" %d", heap[i].pop());
		printf("\n");
	}
	printf("\n");
}

以上のように、接続リストを使用して最後のノードを検索すると(上のコードでfindNode関数が見つかります)、実行速度が損なわれます.逆に、割り当てられたメモリプールの最大割り当て回数は1000000であるため、メモリ領域に関する問題が解決される.これには、問題の制限と要件を特定し、対応するデータ構造を実施する必要があります.メモリ容量の問題がない場合は、アレイを使用して実装することをお勧めします.