Min-Max Heap

src.cpp

#include <cstdio>
#include <cstdlib>
#include <cstring>

#define HEAPSIZE 10000

typedef long long int64;
typedef unsigned int uint;

struct Item {
	int64 key;
	int64 value;
};

struct Node {
	Item item;
	int64 op_idx;
};

struct MMHeap {
	Node min_heap[HEAPSIZE];
	Node max_heap[HEAPSIZE];
	uint len;
};

void init_mmheap(MMHeap* p_heap) {
	p_heap->len = 0;
}

int push_mmheap(MMHeap* p_heap, int64 key, int64 value) {

	uint len = p_heap->len, cur, min_heap_idx;
	Node* min_heap = p_heap->min_heap;
	Node* max_heap = p_heap->max_heap;

	if (len >= HEAPSIZE - 1) {
		return -1;
	}

	cur = len + 1;
	while(cur > 1 && key < min_heap[cur >> 1].item.key) {
		memcpy(min_heap + cur, min_heap + (cur >> 1), sizeof(Node));
		max_heap[min_heap[cur].op_idx].op_idx = cur;
		cur >>= 1;
	}
	min_heap[cur].item.key = key;
	min_heap[cur].item.value = value;
	min_heap_idx = cur;

	cur = len + 1;
	while(cur > 1 && key > max_heap[cur >> 1].item.key) {
		memcpy(max_heap + cur, max_heap + (cur >> 1), sizeof(Node));
		min_heap[max_heap[cur].op_idx].op_idx = cur;
		cur >>= 1;
	}
	max_heap[cur].item.key = key;
	max_heap[cur].item.value = value;

	max_heap[cur].op_idx = min_heap_idx;
	min_heap[min_heap_idx].op_idx = cur;

	p_heap->len += 1;

	return 0;
}

int pop_min_mmheap(MMHeap* p_heap, Item* p_out_item) {
	
	uint len = p_heap->len, key, cur, midx, max_heap_idx;
	Node* min_heap = p_heap->min_heap;
	Node* max_heap = p_heap->max_heap;

	if (len <= 0) {
		return -1;
	}

	memcpy(p_out_item, &(min_heap[1].item), sizeof(Item));
	max_heap_idx = min_heap[1].op_idx;
	key = min_heap[len].item.key;

	cur = 1;
	while (1) {
		if ((cur << 1) >= len) break;
		if (((cur << 1) + 1) >= len) {
			midx = cur << 1;
		} else if (min_heap[cur << 1].item.key < min_heap[(cur << 1) + 1].item.key) {
			midx = cur << 1;
		} else {
			midx = (cur << 1) + 1;
		}
		if (key > min_heap[midx].item.key) {
			memcpy(min_heap + cur, min_heap + midx, sizeof(Node));
			max_heap[min_heap[cur].op_idx].op_idx = cur;
			cur = midx;
		} else {
			break;
		}
	}
	if (cur < len) {
		memcpy(min_heap + cur, min_heap + len, sizeof(Node));
		max_heap[min_heap[cur].op_idx].op_idx = cur;
	}

	key = max_heap[len].item.key;
	cur = max_heap_idx;
	while (1) {
		if ((cur << 1) >= len) break;
		if (((cur << 1) + 1) >= len) {
			midx = cur << 1;
		} else if (max_heap[cur << 1].item.key > max_heap[(cur << 1) + 1].item.key) {
			midx = cur << 1;
		} else {
			midx = (cur << 1) + 1;
		}
		if (key < max_heap[midx].item.key) {
			memcpy(max_heap + cur, max_heap + midx, sizeof(Node));
			min_heap[max_heap[cur].op_idx].op_idx = cur;
			cur = midx;
		} else {
			break;
		}
	}
	while (cur > 1 && key > max_heap[cur >> 1].item.key) {
		memcpy(max_heap + cur, max_heap + (cur >> 1), sizeof(Node));
		min_heap[max_heap[cur].op_idx].op_idx = cur;
		cur >>= 1;
	}
	if (cur < len) {
		memcpy(max_heap + cur, max_heap + len, sizeof(Node));
		min_heap[max_heap[cur].op_idx].op_idx = cur;
	}

	p_heap->len -= 1;

	return 0;
}

int pop_max_mmheap(MMHeap* p_heap, Item* p_out_item) {
	
	uint len = p_heap->len, key, cur, midx, min_heap_idx;
	Node* min_heap = p_heap->min_heap;
	Node* max_heap = p_heap->max_heap;

	if (len <= 0) {
		return -1;
	}

	memcpy(p_out_item, &(max_heap[1].item), sizeof(Item));
	min_heap_idx = max_heap[1].op_idx;

	key = max_heap[len].item.key;
	cur = 1;
	while (1) {
		if ((cur << 1) >= len) break;
		if (((cur << 1) + 1) >= len) {
			midx = cur << 1;
		} else if (max_heap[cur << 1].item.key > max_heap[(cur << 1) + 1].item.key) {
			midx = cur << 1;
		} else {
			midx = (cur << 1) + 1;
		}
		if (key < max_heap[midx].item.key) {
			memcpy(max_heap + cur, max_heap + midx, sizeof(Node));
			min_heap[max_heap[cur].op_idx].op_idx = cur;
			cur = midx;
		} else {
			break;
		}
	}
	if (cur < len) {
		memcpy(max_heap + cur, max_heap + len, sizeof(Node));
		min_heap[max_heap[cur].op_idx].op_idx = cur;
	}

	key = min_heap[len].item.key;
	cur = min_heap_idx;
	while (1) {
		if ((cur << 1) >= len) break;
		if (((cur << 1) + 1) >= len) {
			midx = cur << 1;
		} else if (min_heap[cur << 1].item.key < min_heap[(cur << 1) + 1].item.key) {
			midx = cur << 1;
		} else {
			midx = (cur << 1) + 1;
		}
		if (key > min_heap[midx].item.key) {
			memcpy(min_heap + cur, min_heap + midx, sizeof(Node));
			max_heap[min_heap[cur].op_idx].op_idx = cur;
			cur = midx;
		} else {
			break;
		}
	}
	while (cur > 1 && key < min_heap[cur >> 1].item.key) {
		memcpy(min_heap + cur, min_heap + (cur >> 1), sizeof(Node));
		max_heap[min_heap[cur].op_idx].op_idx = cur;
		cur >>= 1;
	}
	if (cur < len) {
		memcpy(min_heap + cur, min_heap + len, sizeof(Node));
		max_heap[min_heap[cur].op_idx].op_idx = cur;
	}

	p_heap->len -= 1;

	return 0;
}

int main2(void)
{
	MMHeap heap;
	Item item;
	int num;
	int64 tmp;
	int isMax;

	init_mmheap(&heap);
	scanf("%d", &num);
	printf("PUSH start\n");
	for(int i=0; i<num; i++) {
		scanf("%lld", &tmp);
		push_mmheap(&heap, tmp, tmp);
	}
	printf("PUSH complete, POP start\n");
	for(int i=0; i<num; i++) {
		scanf("%d %lld", &isMax, &tmp);
		if (isMax) {
			pop_max_mmheap(&heap, &item);
		} else {
			pop_min_mmheap(&heap, &item);
		}
		if (item.key != tmp) {
			printf("Fail! (Answer: %lld, Key: %lld)\n", tmp, item.key);
			return -1;
		}
	}
	printf("POP end, Success!\n");

	return 0;
}

int main(void)
{
	char cmd[32];
	Item item;
	MMHeap heap;
	int64 tmp;
	init_mmheap(&heap);

	while(1) {
		printf("\n> ");
		scanf("%s", cmd);
		if (strcmp(cmd, "Pm") == 0) {
			if (pop_min_mmheap(&heap, &item)) {
				printf("Fail\n");
				continue;
			}
			printf("Pop min value: %lld\n", item.key);
		} else if (strcmp(cmd, "PM") == 0) {
			if (pop_max_mmheap(&heap, &item)) {
				printf("Fail\n");
				continue;
			}
			printf("Pop min value: %lld\n", item.key);
		} else if (strcmp(cmd, "PUSH") == 0) {
			scanf("%lld", &tmp);
			if (push_mmheap(&heap, tmp, tmp)) {
				printf("Fail\n");
				continue;
			}
			printf("Pushed %lld\n", tmp);
		} else if (strcmp(cmd, ".exit") == 0) {
			break;
		} else if (strcmp(cmd, "PRINT") == 0) {
			for(uint i = 1; i <= heap.len; i++) {
				printf(
					"(%lld, %lld) (%lld, %lld)\n",
					heap.min_heap[i].item.key,
					heap.min_heap[i].op_idx,
					heap.max_heap[i].item.key,
					heap.max_heap[i].op_idx
				);
			}
		} else {
			printf("Command not found\n");
		}
	}

	return 0;
}