The following script searches for the parents of all installed dependencies.

function get_installed_packages() {
    apt list --installed | sed 's#/.*##'
}

function get_installed_packages_with_deps() {
    dpkg-query --show --showformat '${Package} ${Depends} ${Pre-Depends}\n' $(get_installed_packages) \
        | sed 's/ ([^(]*)//g; s/:any\|,//g'
}

function get_package_relations() {
    awk '{print $1 " " $1; for(i = 2; i <= NF; i++) print $1 " " $i;}'
}

function add_marker() {
    echo "~ ~"
}

function resolve_parents() {
    tsort | sed -n '1,/~/ p' | head -n -1
}

(get_installed_packages_with_deps | get_package_relations; add_marker) | resolve_parents

I used tsort in this script. I assume that when adding a marker at the end without dependencies the marker will also be the last entry without dependencies in my result. So I can differenciate between the last package without dependencies and the first package with depenencies.

I noticed one problem with this solution:
There are cycles in the dependency graph. Those entries are ignored by tsort.

The following shell script searches for the parents of all installed dependencies.

function get_installed_packages() {
    apt list --installed | sed 's#/.*##'
}

function get_installed_packages_with_deps() {
    dpkg-query --show --showformat '${Package} ${Depends} \
        ${Pre-Depends}\n' $(get_installed_packages) |  
    sed 's/ ([^(]*)//g; s/:any\|,//g'
}

function get_package_relations() {
    awk '{print $1 " " $1; for(i = 2; i <= NF; i++) print $1 " " $i;}'
}

function add_marker() {
    echo "~ ~"
}

function resolve_parents() {
    tsort | sed -n '1,/~/ p' | head -n -1
}

(get_installed_packages_with_deps | get_package_relations; add_marker) |  
resolve_parents

I used tsort in this script. I assume that when adding a marker at the end without dependencies the marker will also be the last entry without dependencies in my result. So I can differenciate between the last package without dependencies and the first package with depenencies.

I noticed one problem with this solution:
There are cycles in the dependency graph. Those entries are ignored by tsort.