heap_success_code_save_1.07.2020

<?php




class Input {
    /**
     * @var $operation int | null
     */
    private $operation = null;
    /**
     * @var $value int | null
     */
    private $value = null;

    public function __construct( $operation, $value ) {
        $this->operation = (int) $operation;
        if ( $value !== null ) {
            $this->value = (int) $value;
        }
    }

    /**
     * @return int
     */
    public function get_operation() {
        return $this->operation;
    }

    /**
     * @return int
     */
    public function get_value() {
        return $this->value;
    }
}

/**
 * @param $input string
 *
 * @return array<Input>
 */
function get_valid_inputs( $input ) {

    $lines = explode( "\n", $input );

    // Remove first line, not needed
    array_shift( $lines );


    $inputs = array();
    foreach ( $lines as $line ) {
        $parts     = explode( " ", $line );
        $operation = $parts[0];
        $value     = array_key_exists( 1, $parts ) ? $parts[1] : null;
        $inputs[]  = new Input( $operation, $value );
    }

    return $inputs;


}

function get_left_index( $i ) {
    return (int) $i * 2;
}

function get_right_index( $i ) {
    return (int) ( $i * 2 ) + 1;
}

function get_parent_index( $i ) {
    return (int) floor( $i / 2 );
}


class Heap {

    public $storage = array( PHP_INT_MAX );

    public function insert( $value ) {
        // insert at the last then heapify with parent.
        $last_index                   = count( $this->storage );
        $this->storage[ $last_index ] = $value;
        $this->insert_heapify( $last_index );
    }

    public function print_minimum() {
        // there may be a min value in adjacent leaf node.
        echo $this->get_min();
    }

    public function remove( $value ) {
        // find the value in min heap.
        $target_index = $this->get_remove_index( $value );
        if ( ! $target_index ) {
            // dont remove any thing, return early.
            return true;
        }


        $last_element = $this->storage[ count( $this->storage ) - 1 ];
        unset( $this->storage[ count( $this->storage ) - 1 ] );

        if ( $target_index === count( $this->storage ) ) {
            // no need to heapify.
            return true;
        }


        // After unsetting check if the count is 1.
        if ( count( $this->storage ) === 1 ) {
            // we dont need to swap for this one.
            return true;
        }
        // Swap the remove value with the last element value.
        $this->storage[ $target_index ] = $last_element;

        // then delete heapify.
        return $this->delete_heapify( $target_index );
    }

    private function insert_heapify( $index ) {
        $current_val  = $this->storage [ $index ];
        $parent_index = get_parent_index( $index );
        $parent_value = $this->get_parent_value( $index );
        if ( ! $parent_value || $parent_index === 0 ) {
            return true;
        }
        if ( $current_val < $parent_value ) {

            $this->swap( $index, $current_val, $parent_index, $parent_value );

            return $this->insert_heapify( $parent_index );
        } else {
            return true;
        }
    }

    private function get_parent_value( $index ) {
        $parent_index = get_parent_index( $index );

        return array_key_exists( $parent_index, $this->storage )
            ? $this->storage[ $parent_index ] : false;
    }

    private function swap( $idx1, $val1, $idx2, $val2 ) {
        $this->storage[ $idx1 ] = $val2;
        $this->storage[ $idx2 ] = $val1;
    }

    /**
     * @param $value
     *
     * @return bool|int
     */
    private function get_remove_index( $value ) {

        for ( $i = 1; $i < count( $this->storage ); $i ++ ) {
            if ( $value === $this->storage[ $i ] ) {
                return $i;
            }
        }

    }

    private function delete_heapify( $index ) {
        $node_value = $this->storage[ $index ];

        $right_index = get_right_index( $index );
        $left_index  = get_left_index( $index );
        $right_value = array_key_exists( $right_index, $this->storage ) ?
            $this->storage[ $right_index ] : null;
        $left_value  = array_key_exists( $left_index, $this->storage ) ?
            $this->storage[ $left_index ] : null;
        if ( ! $right_value && ! $left_value ) {
            return true;
        }

        $data = $this->get_target_index_and_value( $left_value, $right_value, $left_index, $right_index );


        $target_index = $data['target_index'];
        $target_value = $data['target_value'];

        $this->swap( $index, $node_value, $target_index, $target_value );

        // after swap, heapify the target index.
        return $this->delete_heapify( $target_index );
    }

    /**
     * @param $left_value
     * @param $right_value
     * @param $left_index
     * @param $right_index
     *
     * @return array
     */
    private function get_target_index_and_value( $left_value, $right_value, $left_index, $right_index ) {
        $target_index = $target_value = null;
        if ( ! $left_value ) {
            $target_index = $right_index;
            $target_value = $right_value;
        } else if ( ! $right_value ) {
            $target_index = $left_index;
            $target_value = $left_value;
        } else {
            if ( $left_value < $right_value ) {
                $target_value = $left_value;
                $target_index = $left_index;
            } else {
                $target_value = $right_value;
                $target_index = $right_index;
            }
        }

        return array( 'target_index' => $target_index, 'target_value' => $target_value );
    }

    /**
     * @return mixed
     */
    private function get_min() {
        if ( array_key_exists( 2, $this->storage ) && is_numeric( $this->storage[2] ) ) {
            return min( $this->storage[1], $this->storage[2] );
        } else {
            return $this->storage[1];
        }
    }


}


















$heap = new Heap();

$lines = (int) fgets(STDIN);
$i = 0;


while ( $i < $lines ) {

    $line = fgets(STDIN);
    $parts = explode(" ", $line);

    if ( count($parts) === 2) {
        $operation = intval($parts[0]);
        $value = intval($parts[1]);
        if ( $operation === 1 ) {
            $heap->insert( $value );
        }
        else {
            $heap->remove( $value );
        }
    }
    else {
        $heap->print_minimum();
        echo "\n";
       
    }

    $i += 1;

}



?>