<?php

$arr = array(
    array('id' => 15, 'parent' => 12),
    array('id' => 10, 'parent' => 12),
    array('id' => 12, 'parent' => 12),
    array('id' => 17, 'parent' => 12),
    array('id' => 21, 'parent' => 15),
    array('id' => 13, 'parent' => 15),
    array('id' => 15, 'parent' => 15),
    array('id' => 25, 'parent' => 15),
    array('id' => 7, 'parent' => 7),
    array('id' => 18, 'parent' => 7),
    array('id' => 4, 'parent' => 7),
    array('id' => 1, 'parent' => 3),
    array('id' => 5, 'parent' => 5),
    array('id' => 2, 'parent' => 7)
);

/* Declare variables */
$parents = array();
$result = array();

/* Get all distinct parents */
for ($x = 0; $x < count($arr); $x++)
    if ((!in_array($arr[$x]['parent'], $parents)))
        $parents[] = $arr[$x]['parent'];

sort($parents);

/* Iterate through each parent and create result array */
for ($i = 0; $i < count($parents); $i++) {

    /* Find parent with matching id */
    for ($x = 0; $x < count($arr); $x++) {
        if (($arr[$x]['parent'] === $parents[$i]) && ($arr[$x]['id'] === $parents[$i])) {
            $result[] = $arr[$x];
            $arr[$x] = NULL;
            break;
        }
    }

    /* No match found, find parent with lowest id */
    if ((count($result) === 0) || ($result[count($result)-1]['parent'] !== $parents[$i])) {
        $lowest = array(
            'key' => -1,
            'value' => -1
        );

        for ($x = 0; $x < count($arr); $x++) {
            if ($arr[$x]['parent'] !== $parents[$i] || (in_array($arr[$x], $result)))
                continue;

            if ($lowest['value'] === -1 || $arr[$x]['id'] < $lowest['value']) {
                $lowest['key'] = $x;
                $lowest['value'] = $arr[$x]['id'];
            }
        }

        $result[] = $arr[$lowest['key']];
        $arr[$lowest['key']] = NULL;
    }

    /* Add the rest of the elements for current parent */
    for ($x = 0; $x < count($arr); $x++) {
        if (($arr[$x] === NULL) || ($arr[$x]['parent'] !== $parents[$i]) || (in_array($arr[$x], $result)))
            continue;

        $lowest = array(
            'key' => -1,
            'value' => -1
        );

        for ($y = 0; $y < count($arr); $y++) {
            if (($arr[$y] === NULL) || $arr[$y]['parent'] !== $parents[$i] || (in_array($arr[$y], $result)))
                continue;

            if (($lowest['value'] === -1) || ($arr[$y]['id'] < $lowest['value'])) {
                $lowest['key'] = $y;
                $lowest['value'] = $arr[$y]['id'];
            }

        }

        $result[] = $arr[$lowest['key']];
        $arr[$lowest['key']] = NULL;
    }

    /* Add the last element for current parent (didn't find any other solution) */
    for ($x = 0; $x < count($arr); $x++)
        if ($arr[$x] !== NULL && $arr[$x]['parent'] === $parents[$i])
            $result[] = $arr[$x];
}

/* Output */
print_r($result);

?>