Проверьте, является ли дерево кучей - PullRequest
Новая
       16

Проверьте, является ли дерево кучей

1 голос
/ 29 апреля 2019

Я пытаюсь создать функцию chkHeapProperty , которая будет проверять, удовлетворяет ли данная куча требованию кучи: "Значение, хранимое в узле, должно быть меньше или равно его дочерним элементам узлы " Пример кучи: 

  1
 / \
2   3

let rec chkHeapProperty heap =
    match heap with
    | EmptyHP -> true
    | HP(root, leftHeap, rightHeap) when root < leftHeap && root < rightHeap -> true

Вот так я и получил. Моя первая идея состояла в том, чтобы обойти все узлы и поместить их в список, а затем перебрать этот список, но я чувствую, что должен быть более эффективный способ и более функциональный. Есть идеи?

1 Ответ

2 голосов
/ 29 апреля 2019

Если корень этого дерева меньше, чем корни обоих его поддеревьев, и , то поддеревья также являются кучами, этот корень также должен быть меньше, чем все элементы поддеревьев.
(Потратьте несколько минут, чтобы убедить себя, что это правда.)

Таким образом, вам не нужно перебирать всех детей и внуков (и так далее), вам нужно только проверить корень каждого поддерева и затем рекурсивно проверить «кучу» поддеревьев.

Это проще, если вы сначала определите вспомогательную функцию, 

let lesser x heap = match heap with
    | EmptyHP -> true
    | HP(root, _, _) -> x <= root

, а затем 

let rec isHeap heap = 
    match heap with
    | EmptyHP -> true
    | HP(r, h1, h2) -> lesser r h1 && lesser r h2 && isHeap h1 && isHeap h2
...