From b48c48fcf48b30314271ba88a3b7fbd9d491ef09 Mon Sep 17 00:00:00 2001 From: RossTheRoss Date: Mon, 2 Mar 2020 13:09:39 -0600 Subject: Do 4041 HW --- csci4041/hw2prob2.py | 2 ++ csci4041/hw2prob3.py | 28 ++++++++++++++++++++++++++++ 2 files changed, 30 insertions(+) create mode 100644 csci4041/hw2prob3.py (limited to 'csci4041') diff --git a/csci4041/hw2prob2.py b/csci4041/hw2prob2.py index c52b397..39e533a 100644 --- a/csci4041/hw2prob2.py +++ b/csci4041/hw2prob2.py @@ -14,3 +14,5 @@ def make_sets(n, k): making_sets(n, k, 1, set()) make_sets(4,3) +print() +make_sets(6,1) diff --git a/csci4041/hw2prob3.py b/csci4041/hw2prob3.py new file mode 100644 index 0000000..9fd64b3 --- /dev/null +++ b/csci4041/hw2prob3.py @@ -0,0 +1,28 @@ +def CHILD(i,j): + return 2*i + (j+1) +def IS_IN_MIN_HEAP(A,e): + return FIND_ELEMENT(A,0,e) +def FIND_ELEMENT(A,i,e): + if A[i] is e: + return True + elif CHILD(i,0) < len(A) and A[CHILD(i,0)] <= e: + return IS_IN_MIN_HEAP(A[1:],e) + if CHILD(i,1) < len(A) and A[CHILD(i,1)] <= e: + return IS_IN_MIN_HEAP(A[2:],e) + return False + +#TEST MIN-HEAP +#Feel free to redefine as much as you want +l = [0, 2, 4, 5, 8, 12, 20] + +#TESTS +print(IS_IN_MIN_HEAP(l, 0)) +print(IS_IN_MIN_HEAP(l, 1)) +print(IS_IN_MIN_HEAP(l, 2)) +print(IS_IN_MIN_HEAP(l, 3)) +print(IS_IN_MIN_HEAP(l, 4)) +print(IS_IN_MIN_HEAP(l, 5)) +print(IS_IN_MIN_HEAP(l, 8)) +print(IS_IN_MIN_HEAP(l, 10)) +print(IS_IN_MIN_HEAP(l, 11)) +print(IS_IN_MIN_HEAP(l, 20)) -- cgit v1.2.3