宿題を手伝っている感じがしますが…
オブジェクトを使って、ループ内のコードを簡単にしようとしてます。配列に比べると、オブジェクトだと持ち回しができるのでコードの見通しが良くなると思っています。その代わりHTML変換で再帰呼び出しになってしまいました。

ざっと書いただけなので、ちゃんと書くなら、
・stdClassではなくてHoge用のクラスを使う、
・エラー処理を行う、
など必要なことはたくさんありそうです。


    // オブジェクトに変換する
    $hogeAll = [];
    foreach($data as $hoge) {
        $hogeAll[$hoge['hoge_id']] = makeHoge($hoge);
    }
    // 階層構造を構築する
    $root = [];
    foreach($hogeAll as $hoge) {
        if($hoge->parent>0) {
            $hogeAll[$hoge->parent]->children[] = $hoge;
        } else {
            $root[] = $hoge;
        }
    }
    // HTMLに変換する
    echo listHoge($root);
    
    /**
     * @param stdClass[] $hogeList
     * @param string     $head
     * @return string
     */
    function listHoge(array $hogeList, $head='') {
        $string = "{$head}<ul>";
        foreach($hogeList as $hoge) {
            $string .= "\n{$head}  <li>".$hoge->val;
            if($hoge->children) {
                $string .= "\n{$head}  ".listHoge($hoge->children, "{$head}  ")."\n{$head}";
            }
            $string .= "</li>";
        }
        return $string."\n{$head}</ul>";
    }
    
    /**
     * @param array $data
     * @return stdClass
     */
    function makeHoge($data) {
        $hoge           = new stdClass();
        $hoge->id       = $data['hoge_id'];
        $hoge->val      = $data['hoge'];
        $hoge->parent   = $data['parent_id'];
        $hoge->children = [];
        return $hoge;
    }