败者树

Sep 10, 2011 • {"display_name"=>"pensz", "login"=>"pensz", "email"=>"email", "url"=>""}

很多时候看起来很简单，但是最好自己写一写，这样理解才会更加深刻一些。下面是今天练手写的败者树php实现。

// 测试数据
$data_input = array(
    array(2, 5, 10, 14, 20, 21, 23, 25, 30),
    array(1, 6, 9,  13, 17),
    array(3, 8, 12, 16, 19),
    array(4, 7, 11, 15, 18),
);

// 调用代码示例
k_merge($data_input); 
find_x($data_input, 10);


global $b, $k; // $b 为败者树上的叶子结点值， $k为归并的路数量
define('MINVALUE', -65535); // 定义最小值
define('MAXVALUE', 65536); // 定义最大值

/**
 * k 路归并排序
 */
function k_merge($data_input) {
    global $b, $k;
    $k = count($data_input);

    for ($i = 0; $i< $k; $i++) {
        $b[$i] = array_shift($data_input[$i]);
    }

    $loser_tree = array();
    create_loser_tree($loser_tree);

    while ($b[$loser_tree[0]] !== MAXVALUE){
        $key = $loser_tree[0];
        $value = $b[$key];
        print "\n " . $value . " from $key" ;
        $b[$key] = array_shift($data_input[$key]);
        $b[$key] = $b[$key] === null ? MAXVALUE : $b[$key];
        adjust_loser_tree($loser_tree, $key);
    }
}

/**
 * 从 k 段有序序列中找到 第 x 小的数据
 */
function find_x($data_input, $x) {
    global $b, $k;
    $k = count($data_input);

    for ($i = 0; $i< $k; $i++) {
        $b[$i] = array_shift($data_input[$i]);
    }

    $loser_tree = array();
    create_loser_tree($loser_tree);

    for ($x_i = 1; $x_i <= $x - 1; $x_i++) {
        $key = $loser_tree[0];
        $value = $b[$key];
        // print "\n -- $key " . $value ;
        $b[$key] = array_shift($data_input[$key]);
        $b[$key] = $b[$key] === null ? MAXVALUE : $b[$key];
        adjust_loser_tree($loser_tree, $key);
    }

    $key = $loser_tree[0];
    $value = $b[$key];
    print "\n" . $value . "\n";
}

/**
 * 创建败者树
 */
function create_loser_tree(&$loser_tree) {
    global $b, $k;
    $b[$k] = MINVALUE; //下面初始化调整败者树会用到

    for ($i = 0; $i<$k; $i++) {
        $loser_tree[$i] = $k;
    }

    for ($i = $k - 1; $i >=0; $i--) {
        adjust_loser_tree($loser_tree, $i);
        // var_dump(" adjusted $i", $loser_tree);
    }
}

/**
 * 重新调整败者树
 */
function adjust_loser_tree(&$loser_tree, $s) {
    global $b, $k;
    $t = intval(($s + $k) / 2);

    while ($t > 0) {
        if ($b[$s] > $b[$loser_tree[$t]]) {
            $temp = $s;
            $s = $loser_tree[$t];
            $loser_tree[$t] = $temp;
        }
        $t = intval($t / 2);
    }
    
    $loser_tree[0] = $s;
}