J. W. J. Williams

John William Joseph (Bill) Williams (September[1][2] 1930 – 29 September 2012)[2][3] was a computer scientist best known for inventing heapsort and the binary heap data structure in 1963 while working for Elliot Bros. (London) Ltd.[4][5][6][7]

Personal life

He was born in England,[8] in the district of Chippenham in Wiltshire County,[1] to William Henry Williams[3] and his wife (née Haines).[1]

On 3 March 1962 he married[8] age 31) married Ann[2][5] Zerny (a nurse,[5] age 23) at Christ Church in Chorleywood Parish in Hertfordshire County.[3] They had three children.[2]

In 1974, he moved to Ottawa, Ontario, Canada.[2][5][8]

He died on 29 September 2012 at age 82.[2]

Career

In 1952, he received a B.Sc. in mathematics from King's College, University of London.[8]

In England, he worked as a programmer for Elliot Automation,[8] formerly Elliot Brothers (London) Limited, where he invented heapsort and used it to create the event-driven Elliott Simulator Package (ESP) with the help of C. A. R. (Tony) Hoare.[4][5][9] He also worked for English Electric and GEC.[8] He worked with Donald E. Knuth to develop a two-heap data structure that they called a "priority deque", published as an exercise in The Art of Computer Programming in 1973.[10][11]

After moving to Canada in 1974, he worked for Bell-Northern Research Ltd., Ottawa (BNR) and Northern Telecom (Nortel) until retiring in 1995.[2][5] At BNR, he worked on various software and hardware systems such as the DMS-100 digital telephone switch, publishing a paper about their software in June 1982.[8]

References

  1. 1 2 3 "Record Transcription: England & Wales Births 1837-2006". Findmypast. brightsolid online publishing ltd. Retrieved 2 November 2023. First name(s): John W J, Last name: Williams, Birth quarter: 4, Birth year: 1930, Mother's maiden name: Haines, District: Chippenham, County: Wiltshire
  2. 1 2 3 4 5 6 7 "J.W.J. WILLIAMS Obituary (2012)". Ottawa Citizen. 4 October 2012. Retrieved 20 September 2023 – via Legacy Remembers.
  3. 1 2 3 Marriage certificate for John William Joseph Williams and Ann Zerny, 3 March 1962.
    GRO Reference Information: Year=1962, Qtr=M, Vol=04B, Page=686 (from https://www.familysearch.org/ark:/61903/1:1:QV64-HY9Y)
    Text of document (ordered from https://www.gro.gov.uk/):
    CERTIFIED COPY OF AN ENTRY OF MARRIAGE
    Given at the GENERAL REGISTER OFFICE 1962. Marriage solemnized at Christ Church in the Parish of Chorleywood in the County of Herts No: 61
    When married: March 3rd, 1962
    Name and surname: John William Joseph Williams / Ann Zerny
    Age: 31 / 23
    Condition: Bachelor / Spinster
    Bank or profession: Mathematician / Staff Nurse
    Residence at the time of marriage: 1, Windham Cottage, Wild Hill, Hatfield / <redacted as per WP:BLPPRIVACY>
    Father's name and surname: William Henry Williams (Deceased) / <redacted as per WP:BLPNAME>
    Rank or profession of father: <not specified> / <redacted as per WP:BLPPRIVACY> Married in the Parish Church according to the rites and ceremonies of the Established Church after Banns by me, John H. G. Gilliet, Vicar.
    This marriage was solemnized between us, } John William Joseph Williams / Ann Zerny } in the presence of us, { <redacted as per WP:BLPNAME>. CERTIFIED to be a true copy of an entry in the certified copy of a register of Marriages in the Registration District of Watford
    Given at the General Register Office, under the Seal of the said Office, the 5th day of October 2023
    MXJ 769947
    2340156 04/23 APS/A1SP
  4. 1 2 Williams, J. W. J. (June 1964) [Received 1 October 1963, revised 15 February 1964.]. Forsythe, G. E. (ed.). "Algorithm 232: Heapsort". Algorithms. Communications of the ACM. 7 (6): 347–348. doi:10.1145/512274.3734138. ISSN 0001-0782 – via ACM Digital Library. Elliott Bros. (London) Ltd., Borehamwood, Herts, England
  5. 1 2 3 4 5 6 Hantman, Nancy T. (December 1997). "And the winners are ... Spectrum's Second Quilt Block Contest". IEEE Spectrum. 34 (12): 49. doi:10.1109/MSPEC.1997.642968. eISSN 1939-9340. ISSN 0018-9235. COMPUTERS/FABRIC: Heapsort by J. W. J. (Bill) and Ann Williams, Kanata, Ont., Canada.
  6. ↑ Brodal, Gerth Stølting; Pinotti, M. Cristina (1998). "Comparator networks for binary heap construction". In Arnborg, Stefan; Ivansson, Lars (eds.). Algorithm Theory — SWAT'98. Lecture Notes in Computer Science. Vol. 1432. Berlin, Heidelberg: Springer. pp. 158–168. doi:10.1007/BFb0054364. hdl:11858/00-001M-0000-0014-9A0B-B. ISBN 978-3-540-69106-8.
  7. ↑ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (19 May 2012). "Strict fibonacci heaps". Proceedings of the forty-fourth annual ACM symposium on Theory of computing. STOC '12. New York, NY, USA: Association for Computing Machinery. pp. 1177–1184. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5. S2CID 3107885.
  8. 1 2 3 4 5 6 7 Penney, Brian K.; Williams, J. W. J. (June 1982) [Manuscript received 21 July 1981; revised 17 December 1981.]. "The Software Architecture for a Large Telephone Switch". IEEE Transactions on Communications. COM-30 (6): 1369–1378. doi:10.1109/TCOM.1982.1095594. eISSN 1558-0857. ISSN 0090-6778.
  9. ↑ Williams, J. W. J. (1 January 1964). "E.S.P. The Elliott Simulator Package". The Computer Journal. 6 (4). The British Computer Society: 328–331. doi:10.1093/comjnl/6.4.328 – via Oxford Academic, Oxford University Press.
  10. ↑ Sepesi, Greg (14 June 2007). "Dualheap Selection Algorithm: Efficient, Inherently Parallel and Somewhat Mysterious". arXiv:0706.2155v1 [cs.DS].
  11. ↑ Knuth, Donald Ervin (1973). "5.2.3 Sorting by Selection, Exercise 31". The Art of Computer Programming: Sorting and searching. Vol. 3 (1st ed.). Addison-Wesley Publishing Company. p. 159. ISBN 978-0-201-03803-3.