checking if a tree is a heap [in prolog]

Question

I need some help writing a predicate heap(Tree) in prolog that succeeds if Tree is a heap that satisfies both the heap property and the shape property:

• The shape property: the tree is an almost complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• The heap property: each node is greater than or equal to each of its children according to some comparison predicate which is fixed for the entire data structure.

I would like to write 2 predicates using 2 different representations:

1. node(K,L,R) to represent a tree with key K (an integer), left subtree L and right subtree R

2. list of integers, from the root to leaf, left to right

For example:

?- heap1(node(5, node(4, empty, empty), empty)).
true.

and

?- heap2([5, 4, 3, 2]).
true
?- heap2([7, 6, -1, -3, 5]).
true
?- heap2([]).
true

I currently have very limited knowledge of Prolog and need a lot of helps defining these predicates. Thanks!

Answer 1

I'm your instructor, i know your IP address and I know your CDF login. Please come and see me asap in my office.

Answer 2

At least take the effort to re-word the question if you're going to ask the internet at large for help... you straight up copy pasted that. I'm in the same course so don't even try and deny it lmao.

Answer 3

_{This question was deleted right after it was originally posted, because the OP was not upfront about the fact that she asked a homework question. As the due date for the assignment has since passed, I have decided to undelete this answer.}

I'm not a Prolog guru, but I gave your question some thought. I think heap1/1 is easier to implement than heap2/1, because its "tree structure" is more apparent. In fact, what I will do is implement heap1/1, after which I'll implement heap2/1 in terms of heap1/1.

The tree implementation: heap1/1

The empty tree is a binary heap. As for node(K, L, R), it is a heap if:

1. L and R are heaps.
2. If L and/or R are not empty, then their key is less than or equal to K.
3. If L has depth d, then R has depth d or d - 1.

So what needs to be done, is to check whether a given binary tree satisfies those properties.

• Given a node, we will need to traverse it to know the depth of the tree it represents. Hence we will define heap/1 in terms of a predicate heap/2, in which the second argument is the tree depth. In the end we don't care about the actual depth, so we define:

  heap1(H) :- heap1(H, _).
  

• So what about heap/2? The base case is empty, which is a heap with depth 0 (or 1, but that is irrelevant for our purposes). Thus:

  heap1(empty, 0).
  

• For node(K, L, R) we'll have to recurse. We need to test the heap properties outlined above and calculate the tree depth H. Thus:

  heap1(empty, 0).
  heap1(node(K, L, R), H) :-
    heap1(L, LH), heap1(R, RH),
    (L = node(LK, _, _) *-> K @>= LK; true),
    (R = node(RK, _, _) *-> K @>= RK; true),
    (LH is RH; LH is RH + 1), H is LH + 1.
  

  This code uses SWI-Prolog's soft cut (*->)/2. This mechanism is used to test whether the subtrees are non-empty, and if so, to verify that their key is smaller or equal to K (using (@>=)/2). The predicate true/0 corresponds to the situation in which one of the subtrees is empty. (is)/2 is used to compare the depths of the subtrees and to calculate the depth of the whole tree.

The list implementation: heap2/1

I assume that heap2/1 is supposed to check whether its sole argument is a list representing a heap stored as an array (or Ahnentafel list). If so, then, assuming a zero-indexed list, the children of a node at index i are found at indices 2i + 1 and 2i + 2.

• As a result, a parent node is not necessarily stored right next to its child nodes. More specifically, at position i in the list we'll need to skip i or i + 1 places to reach the keys of the subtrees. We'll define a predicate skipn/3 to help us with that:

  skipn(N, L, E) :- (length(F, N), append(F, E, L)) *-> true; E = [].
  

  skipn(N, L, E) succeeds if E equals L after the first N elements of L have been stripped or if E is the empty list while the length of L is not greater than N. This implementation uses length/2, append/3 and again (*->)/2 and true/0.

• Next up: the definition of heap2/1. Again we will call in the help of an auxiliary predicate, this time heap2/3. heap2(H, N, T) succeeds if the list H, of which the head is at position N of a possibly greater list, can be converted to a binary tree T. heap2/1 will call heap2/3 with initial index 0 and will verify that the resulting binary tree is in fact a heap. Thus:

  heap2(H) :- heap2(H, 0, T), heap1(T).
  

• Alright, we're almost there. At position N the index LI of the root of the left subtree is 2 * N + 1. Likewise RI = 2 * N + 2 is the index of the root of the right subtree. Since at position N already N list items have been skipped, only LI - N and RI - N elements need to be skipped to reach indices LI and RI, respectively. Thus:

  heap2([], _, empty).
  heap2([H|T], N, node(H, L, R)) :-
    LI is 2 * N + 1, RI is 2 * N + 2,
    LS is LI - N, RS is RI - N,
    skipn(LS, [H|T], LT), skipn(RS, [H|T], RT),
    heap2(LT, LI, L), heap2(RT, RI, R).