a) Define a SCHEME procedure, named (heap-insert f x H), which adds element x to heap H using the first-order relation f to determine which element belongs at the root of each (sub)tree. For instance, if we wanted the same behavior as the heaps in the lecture slides (min-heap), we would use the "less than" function as our first-order relation: (heap-insert < 100 (heap-insert < 10 (list))) (10 () (100 (O 0)) If, instead, we wanted a max-heap implementation, where the largest element is at the root of the heap, we would use the "greater than" function as our first-order relation. (heap-insert > 100 (heap-insert > 10 (list))) (100 () (10 (O 0)) Note, you must use the same first-order relation for all of the heap procedures applied to a particular heap structure.

Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Question

Answer using scheme R5RS

(a) Define a SCHEME procedure, named (heap-insert f x H), which adds element x to heap
H using the first-order relation f to determine which element belongs at the root of each
(sub)tree.
For instance, if we wanted the same behavior as the heaps in the lecture slides (min-heap), we
would use the "less than" function as our first-order relation:
(heap-insert < 100 (heap-insert < 10 (list)))
(10 () (100 () O))
If, instead, we wanted a max-heap implementation, where the largest element is at the root of
the heap, we would use the “greater than" function as our first-order relation.
(heap-insert > 100 (heap-insert > 10 (list)))
(100 () (10 () ()))
Note, you must use the same first-order relation for all of the heap procedures applied to a
particular heap structure.
(b) Define a SCHEME procedure, named (combine f Ha Hb), which accepts three arguments,
f, a first-order relation which is used to order the elements in the heap, and two heap struc-
tures, Ha and Hb, which have been constructed using the same first-order relation. For exam-
ple, for two min-heaps
(define Ha Cheap-insert-list > (1ist 957 3) (1ist)))
(define Hb (heap-insert-list > (1ist 2 8 4 6) (list)))
(combine > Ha Hb)
(9 (7 () (5 0 (3 () 0))) (8 (4 () ()) (6 () (2 () ()))))
(c) Define a SCHEME function, named (empty? H) which takes one argument, a heap, and re-
turns a boolean value, true if H is the empty heap and false otherwise.
Transcribed Image Text:(a) Define a SCHEME procedure, named (heap-insert f x H), which adds element x to heap H using the first-order relation f to determine which element belongs at the root of each (sub)tree. For instance, if we wanted the same behavior as the heaps in the lecture slides (min-heap), we would use the "less than" function as our first-order relation: (heap-insert < 100 (heap-insert < 10 (list))) (10 () (100 () O)) If, instead, we wanted a max-heap implementation, where the largest element is at the root of the heap, we would use the “greater than" function as our first-order relation. (heap-insert > 100 (heap-insert > 10 (list))) (100 () (10 () ())) Note, you must use the same first-order relation for all of the heap procedures applied to a particular heap structure. (b) Define a SCHEME procedure, named (combine f Ha Hb), which accepts three arguments, f, a first-order relation which is used to order the elements in the heap, and two heap struc- tures, Ha and Hb, which have been constructed using the same first-order relation. For exam- ple, for two min-heaps (define Ha Cheap-insert-list > (1ist 957 3) (1ist))) (define Hb (heap-insert-list > (1ist 2 8 4 6) (list))) (combine > Ha Hb) (9 (7 () (5 0 (3 () 0))) (8 (4 () ()) (6 () (2 () ())))) (c) Define a SCHEME function, named (empty? H) which takes one argument, a heap, and re- turns a boolean value, true if H is the empty heap and false otherwise.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps

Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY