From ede4ba0d37480186f333ad7d7bb2e3d48a7e7d52 Mon Sep 17 00:00:00 2001 From: Andreas Grois Date: Fri, 2 Aug 2024 20:15:39 +0200 Subject: Proves about heapRemoveLast. --- TODO | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'TODO') diff --git a/TODO b/TODO index c4ed7da..4a6c8e4 100644 --- a/TODO +++ b/TODO @@ -3,10 +3,10 @@ This is a rough outline of upcoming tasks: [ ] Prove that an index exists such that after CompleteTree.heapPush the pushed element can be obtained by CompleteTree.get [ ] Prove that CompleteTree.heapUpdateAt returns the element at the given index -[ ] Prove that CompleteTree.heapRemoveLastWithIndex and CompleteTree.heapRemoveLast yield the same tree -[ ] Prove that CompleteTree.heapRemoveLastWithIndex and CompleteTree.heapRemoveLast yield the same element +[x] Prove that CompleteTree.heapRemoveLastWithIndex and CompleteTree.heapRemoveLast yield the same tree +[x] Prove that CompleteTree.heapRemoveLastWithIndex and CompleteTree.heapRemoveLast yield the same element [x] Prove that CompleteTree.heapRemoveLastWithIndex only removes one element and leaves the rest unchanged - - This automatically serves as a proof for CompleteTree.heapRemoveLast, once it is shown that they + [x] This automatically serves as a proof for CompleteTree.heapRemoveLast, once it is shown that they yield the same tree - Done by showing that each element of the input tree is in the output tree, except for the one at the returned index. -- cgit v1.2.3