troubleshooting Question

How to write a heap function in Scheme

Avatar of speedingcars2012
speedingcars2012 asked on
Programming Languages-OtherProgrammingPuzzles / Riddles
2 Comments1 Solution776 ViewsLast Modified:
I'm taking a computer class that uses Scheme and I'm having tons of trouble with the language. I've programmed with C++ and visual basic before so I understand the general idea of programming but I can never get the Scheme syntax right and a lot of the language is downright clunky. This is the function:

   ; A heap is either
    ; - false
    ; - (make-node number[n] heap[l] heap[r])
    ; INVARIANT: each number in l is larger than n
    ; INVARIANT: each number in r is larger than n

Write the following functions:

    ; in-heap? : heap number -> boolean
    ; determines if n is in h
    (define (in-heap? h n) ---)

    ; insert-in-heap : heap number -> heap
    ; constructs a new heap that contains
    ; all of the numbers in h, plus n
    (define (insert-in-heap h n) ---)

You must exploit/maintain the heap invariant in each function (as appropriate).

I don't really even understand what they're asking for here. I googled heap too death and figured out it was a data structure but I couldn't really figure out the correct way to set it up in a program. And I have no idea where this "r" comes in.

I realize scheme is a icky old language, so if you need a point of reference, we're using an online book at
http://www.htdp.org/2003-09-26/
 
and I'm using the compiler Dr. scheme with the language beginning student with list abbreviations, if that's relevant at all. it's available at
http://download.plt-scheme.org/


;;this is the program I wrote for what I feel would be similar to in-heap? but I'm not sure and I ;;don't know how to apply it to the whole heap invariant idea
 
(define (in? l n)
  (cond
     [(empty? l) false ]
     [(= n (first l)) true ]
     [(< n (first l)) false ]
     [else (in? (rest l) n)]))
 
(in? '(12 13 14 15) 14)
(in? '(5 6 7 8 12) 2)
ASKER CERTIFIED SOLUTION
harfang

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Join our community to see this answer!
Unlock 1 Answer and 2 Comments.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 2 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros