ラケットの優先キュー？

Question

私は次の定義を満たすラケットにおけるプライオリティキュー、（ウィキペディアより）太字で特にビットを探しています：プライオリティキューは、通常のキューまたはスタックのようなものである抽象データ型である

各要素がそれに関連する「優先度」を有する場合には、追加のデータ構造が必要となる。優先度キューでは、優先度の高い要素の前に優先度の高い要素が表示されます。 2つの要素の優先度が同じ場合は、キューの順序に従って配信されます。

私が（実際には）これが理解しているのは、キューに追加された順序に従ってサービスされていることです。

私はラケットのdata/heapを試しましたが、優先順位が同じであれば正しい順序が維持されません。

テストコード：

#lang racket 

(require data/heap) 

(define h (make-heap 
      (λ (p1 p2) 
      (<= (car p1) (car p2))))) 

(define (add! p) (heap-add! h p)) 

(add! '(1 a)) 
(add! '(2 b)) 
(add! '(3 c)) 
(add! '(3 d)) 
(add! '(3 e)) 
(add! '(3 f)) 
(add! '(3 g)) 
(add! '(3 h)) 
(add! '(3 i)) 

(for ([p (in-heap h)]) 
    (display p)) 

出力：

(1 a)(2 b)(3 h)(3 g)(3 f)(3 e)(3 d)(3 c)(3 i) 

私は次の出力が必要になります。

(1 a)(2 b)(3 c)(3 d)(3 e)(3 f)(3 g)(3 h)(3 i) 

Answer 1

は、標準のヒープを使用してください。各挿入のためにインクリメントされるカウンタiを保持する。要素xを優先度キューに挿入するには、ヒープにinsert（list i x）を実行します。あなたの注文述語は今やiを使ってネクタイを破ることができます。