С помощью aptitude вы можете выполнить поиск такого типа.
aptitude search '?priority(required)'
Обратите внимание, что aptitude больше не устанавливается по умолчанию в новых версиях Ubuntu, а его man-страница неполна; вы найдете полную документацию как /usr/share/doc/aptitude/README