Solidity : 최대값 검색을 위한 Heap Tree 구현

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.20;

/**
 * ✅ Max Heap (Binary Heap 기반)
 * - Efficient insert and extractMax (O(log n))
 * - Implemented as a 1-based array (0th index unused)
 */
contract MaxHeap {
    uint[] private heap;

    constructor() {
        heap.push(0); // index 0은 사용하지 않음
    }

    function insert(uint value) external {
        heap.push(value);
        _heapifyUp(heap.length - 1);
    }

    function extractMax() external returns (uint) {
        require(heap.length > 1, "heap is empty");

        uint max = heap[1];
        heap[1] = heap[heap.length - 1];
        heap.pop();
        _heapifyDown(1);
        return max;
    }

    function peekMax() external view returns (uint) {
        require(heap.length > 1, "heap is empty");
        return heap[1];
    }

    function size() external view returns (uint) {
        return heap.length - 1;
    }

    function getAll() external view returns (uint[] memory) {
        uint[] memory result = new uint[](heap.length - 1);
        for (uint i = 1; i < heap.length; i++) {
            result[i - 1] = heap[i];
        }
        return result;
    }

    function _heapifyUp(uint index) internal {
        while (index > 1) {
            uint parent = index / 2;
            if (heap[parent] >= heap[index]) {
                break;
            }
            (heap[parent], heap[index]) = (heap[index], heap[parent]);
            index = parent;
        }
    }

    function _heapifyDown(uint index) internal {
        uint length = heap.length;
        while (2 * index < length) {
            uint left = 2 * index;
            uint right = 2 * index + 1;
            uint largest = index;

            if (heap[left] > heap[largest]) {
                largest = left;
            }
            if (right < length && heap[right] > heap[largest]) {
                largest = right;
            }
            if (largest == index) break;

            (heap[index], heap[largest]) = (heap[largest], heap[index]);
            index = largest;
        }
    }
}

✨ 주요 기능:
• insert(uint) → 값을 힙에 추가 (O(log n))
• extractMax() → 최대값 추출 (O(log n))
• peekMax() → 최대값 확인 (읽기 전용)
• getAll() → 전체 힙 배열 반환
• 내부적으로 1-based 배열로 구현하여 부모/자식 인덱스 계산을 직관적으로 구성

⸻